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

[Chris L T521]

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!

 

[Chris L T521]

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):

Spoiler

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:

Spoiler

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.