Welcome to our community

Be a part of something great, join today!

Problem of the Week #45 - February 4th, 2013

Status
Not open for further replies.
  • Thread starter
  • Moderator
  • #1

Chris L T521

Well-known member
Staff member
Jan 26, 2012
995
Thanks to those who participated in last week's POTW!! Here's this week's problem!

-----

Problem: Does there exist an integer $n$ such that $29\mid n^2-5$? If so, find the smallest such integer.

-----

Remember to read the POTW submission guidelines to find out how to submit your answers!
 
  • Thread starter
  • Moderator
  • #2

Chris L T521

Well-known member
Staff member
Jan 26, 2012
995
This week's problem was correctly answered by Bacterius, jakncoke, and Sudharaka. You can find Sudharaka's answer below (which utilizes the Legendre symbol rather nicely):

This problem is equivalent to solving the following congruence. \[n^2\equiv 5\mbox{ (mod 29)}\]
Consider the Legendre symbol, \(\displaystyle \left(\frac{5}{29}\right)\). By the law of quadratic reciprocity we get,
\[\left(\frac{5}{29}\right)=(-1)^{\left(\frac{5-1}{2}\right)\left(\frac{29-1}{2}\right)}\left(\frac{29}{5}\right)=\left(\frac{4}{5}\right)=\left(\frac{2}{5}\right)^2\]
Since, \(\displaystyle \left(\frac{2}{5}\right)=\pm 1\) we get,
\[\left(\frac{5}{29}\right)=1\]
Therefore the congruence \(n^2\equiv 5\mbox{ (mod 29)}\) has solutions. Substituting values starting from \(0\) we can see that the smallest value which satisfies the congruence is \(11\).

Check out Bacterius' solution for an alternative (yet similar) approach:

The equation $n^2 - 5 \equiv 0 \pmod{29}$ can be written $n \equiv \sqrt{5} \pmod{29}$. Note that:$$5^{\frac{29 - 1}{2}} \equiv 1 \pmod{29}$$
Therefore $5$ is a quadratic residue modulo $29$, and we have two solutions:
$$n \equiv 11 \pmod{29}$$
$$n \equiv 18 \pmod{29}$$
Which gives every possible solution for $n$. The first few solutions are:
$$n = 11 + 0 \cdot 29, 18 + 0 \cdot 29, 11 + 1 \cdot 29, 18 + 1 \cdot 29, \cdots ~ ~ ~ \Longleftrightarrow ~ ~ ~ n = 11, 18, 40, 47, \cdots$$
So the smallest solution is $n = 11$, and there are infinitely many of them.
 
Status
Not open for further replies.