Exercise 3.2.1 ($x^2 \equiv 10 \pmod{89}$ is solvable.)

Question

Verify that $x^2 \equiv 10 \pmod {89}$ is solvable.

Richard Ganaye · Accepted Answer

ewcommand{\legendre}[2]{\genfrac{(}{)}{}{}{#1}{#2}}

\begin{proof} $89$ is a prime number, and
\begin{align*}
\legendre{10}{89} &= \legendre{2}{89} \legendre{5}{89}, 	ext{ where}\
\legendre{2}{89} &= (-1)^{(89^2 - 1)/8} =1,&(89 \equiv 1 \pmod 8)\
\legendre{5}{89} &= \legendre{89}{5}&(5 \equiv 1 \pmod 4)\
&= \legendre{4}{5} =  \legendre{2}{5}^2 = 1.
\end{align*}
Therefore
$$\legendre{10}{89}  = 1,$$
hence $x^2 \equiv 10 \pmod {89}$ is solvable.
\end{proof}
\begin{verbatim}
sage: kronecker(10,89)
1
sage: a = Mod(10, 89)
sage: a.sqrt()
30
\end{verbatim}

Exercise 3.2.1 ($x^2 \equiv 10 \pmod{89}$ is solvable.)

Answers

Comments

Exercise 3.2.1 ($x^2 \equiv 10 \pmod{89}$ is solvable.)

Answers

Comments

Add answer