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?

  • $\begingroup$ 2 is even, 58 is even, 1 is odd $\endgroup$ Nov 8, 2019 at 9:15
  • $\begingroup$ mod by low primes it forces things on the multiplier of 59 that can work, then see if you get an impossibility ? $\endgroup$
    – user645636
    Nov 8, 2019 at 13:53

3 Answers 3


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

  • $\begingroup$ I thought the Legendre symbol is $(\frac{a}{p})=a^{\frac{p-1}{2}}$ mod $p$? $\endgroup$ Nov 8, 2019 at 9:17
  • 2
    $\begingroup$ Yes, that's modulo $p$. We don't want modulo $p$, we want the explicit value $+1$ or $-1$, see here. Then $+1$ means "yes", and $-1$ means "no" for the solvability of $x^2\equiv 2\bmod 59$. No need for more computation with $2^{29}$. $\endgroup$ Nov 8, 2019 at 9:18

$$ x^{58}\equiv1\pmod{59}$$

So, we need to test $2^{29}\pmod{59}$





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.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .