How can I solve $x^2 \equiv 19 \pmod {59}$. How can I solve $x^2 \equiv 19 \pmod {59}$?
I know that we can just try squaring numbers from 1 to 58 , but this is a very slow method, is not their a quicker one?

Hint: You Gauss reciprocity theorem:
$$\Big({19\over 59}\Big)\Big({59\over 19}\Big) = (-1)^{{59-1\over 2}\cdot {19-1\over 2}}= -1$$
Since $$59 \equiv 2\pmod{19}$$ and if $$x\equiv 0,\pm1,\pm2,\pm3,\pm4,\pm5,\pm6, \pm7,\pm8, \pm9 \pmod{19}$$ we have $$x^2\equiv 0,1,4,9,-3,6,-2, -8,6, 5 \pmod{19}$$
we see that $$\Big({59\over 19}\Big)=\Big({2\over 19}\Big) =-1$$
so $$\Big({19\over 59}\Big) =1$$ which means $19$ is a square modulo $59$

Now if you want explicit $x$ then you can use brute force method, if a modulo is not, like in this case, to big:
$$x≡0,±1,±2,±3,±4,±5,...±29(\mod59)$$
and then calculate the square of $x$ and we can see
$14^2≡19(\mod59)$.
