# Elementary theory of numbers and congruences

How to find solutions for:

• $x^2\equiv 8\pmod{ 3}$
• $x^2\equiv 15\pmod{ 31}$
• $x^2\equiv 54\pmod{ 7}$
• $x^2\equiv625\pmod{9973}$
• Make the list.. mmh, nah Jan 10, 2016 at 12:11
• Quadratic reciprocity Jan 10, 2016 at 23:22

The first and third are easy, you just check the $3$ and $7$ cases respectively (you can get away with $1$ and $3$ cases respectively if you're a bit clever). The fourth you can solve by taking the square root. And lastly, the second one, you may look for perfect squares among all the numbers $n\equiv 15 \pmod{31}$. It shouldn't take long.
Let $p$ be an odd prime and $a$ an integer coprime to $p$. Then
$a^{\tfrac{p-1}{2}} \equiv \begin{cases} \;\;\,1\pmod{p}& \text{ if there is an integer }x \text{ such that }a\equiv x^2 \pmod{p}\\ -1\pmod{p}& \text{ if there is no such integer.} \end{cases}$