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?
 A: You can get it by playing around with equivalences modulo $59$ and extracting squares: from
$$x^2 \equiv 19 \equiv -40 \equiv 2^2(-10) \pmod{59}$$
and
$$-10 \equiv 49 \equiv 7^2 \pmod{59},$$
we have $x^2 \equiv 14^2 \pmod{59}$, so $x \equiv \pm 14 \pmod {59}$.
A: Lagrange observed that we can easily compute a square root in groups of odd order $\,\color{#c00}{2n+1},\,$ i.e. the equation $\,x^{\large 2} = a\,$ has solution $\,x = a^{\large n+1}\,$ by $\,x^{\large 2} = a\, a^{\large \color{#c00}{2n+1}} = a,\,$ by Lagrange's Theorem.
Here mod $\,\color{#0a0}{p = 4n+3}\,$ the subgroup $\,S\,$ of squares has odd order $\,(p-1)/2 = 2n+1.\,$ Thus, by above, any square $\,a\in S\,$ has a  square root $\,x = a^{\large n+1}.\,$ Here $\,n\!+\!1 = \color{#0a0}{(p+1)/4} = 15$. 
A: With $\phi(59)=58=2\cdot 29$ we know that all elements of the multiplicative group have order $1,2,29$ or $58$ (see the answer of Bill Dubuque for the named and more general order arguments). Test $$ 19^{29}=1\pmod{59}$$  computationally, giving the order of $19$ as the odd number $29$, which allows to compute a square root from $$19^{2⋅15}=19\pmod{59}.$$ This gives one (the?) pair of square roots as 
$$x=\pm19^{15}=\pm14\pmod{59}.$$
A: Try adding multiples of $59$ to $19$:  $19, 78, 137, \color{red}{196}$
A: 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)$.
