1
$\begingroup$

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?

$\endgroup$
2
  • $\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

3
$\begingroup$

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

$\endgroup$
2
  • $\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
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

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