Exercise 3.2.6 ($x^2 \equiv 150 \pmod{1009}$ is solvable)

Question

Decide wether $x^2 \equiv 150 \pmod{1009}$ is solvable or not.

Richard Ganaye · Accepted Answer

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

\begin{proof} Since $150 = 2 \cdot 3 \cdot 5^2$,
\begin{align*}
\legendre{150}{1009} &= \legendre{2}{1009} \legendre{3}{1009} \legendre{5}{1009}^2 = \legendre{2}{1009} \legendre{3}{1009}, \quad 	ext{where}\
\legendre{2}{1009}&= (-1)^{(1^2 - 1)/8} = 1,\
 \legendre{3}{1009} &=  \legendre{1009} {3} = \legendre{1} {3} = 1,\
\end{align*}
thus
$$\legendre{150}{1009} = 1.$$
Therefore $x^2 \equiv 150 \pmod{1009}$ is solvable (the two solutions are $139, 870$).
\end{proof}

Exercise 3.2.6 ($x^2 \equiv 150 \pmod{1009}$ is solvable)

Answers

Comments

Exercise 3.2.6 ($x^2 \equiv 150 \pmod{1009}$ is solvable)

Answers

Comments

Add answer