Elementary theory of numbers and congruences

Question

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}$

Answer 1

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.

Answer 2

HINT: First use Euler's criterion to make sure that they have solutions. Euler's criterion is a formula for determining whether an integer is a quadratic residue modulo a prime. Precisely,

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}$

Then use Quadratic reciprocity to find those solutions.