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?

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

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

• I thought the Legendre symbol is $(\frac{a}{p})=a^{\frac{p-1}{2}}$ mod $p$? Nov 8, 2019 at 9:17
• 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}$. Nov 8, 2019 at 9:18

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