Determine whether $x^2\equiv 2$ mod $59$ has solutions. 
Determine whether $x^2\equiv 2$ mod $59$ has solutions.

I know Euler's Criterion.
So I want to determine if $2^{58/2}=2^{29}\equiv 1$ mod $59$
However besides computing this with a calculator, I'm not sure how to determine that this is a quadratic residue mod $59$.
Is there a way to do this which has computations that are easier to do by hand?
 A: No, it has no solution since the Legendre symbol is given by
$$
\biggl(\frac{2}{59}\biggr)=(-1)^{(59^2-1)/8}=-1^{435}=-1.
$$
Actually, we do not need to compute $(p^2-1)/8$, it is enough to see that $p=59\equiv 3\bmod 8$.  
A: $$ x^{58}\equiv1\pmod{59}$$
So, we need to test $2^{29}\pmod{59}$
$$2^6\equiv5\pmod{59}\implies2^{18}\equiv5^3\equiv7$$
$$2^{30}=2^{18}(2^6)^2\equiv7\cdot25\equiv-2$$
$$\implies2^{29}\equiv-1\pmod{59}$$
A: A systematic approach to evaluating powers in modular arithmetic is what I call the "squaring and multiplication" method.
Successively divide $29$ by $2$, keeping just the quotients, until you get down to $1$:
$29\to 14\to 7\to 3\to 1$.
So we will evaluate $2^3$, then $2^7$, then $2^{14}$ and finally $2^{29}$:
$2^2\equiv 4\bmod 59$
$2^3\equiv 4×2\equiv 8$
$2^6\equiv 8^2\equiv 5$
$2^7\equiv 5×2\equiv 10$
$2^{14}\equiv 10^2\equiv 41\equiv -18$
$2^{28}\equiv 18^2\equiv 29$
$2^{29}\equiv 29×2\equiv 58\equiv -1$
Well ... that was a bummer.  As lab bhattacharjee also found, the test fails and the original equation has no solution.
