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

Status
Not open for further replies.

#### Chris L T521

##### Well-known member
Staff member
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.

-----

#### Chris L T521

##### Well-known member
Staff member
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.