Exercise 3.2.18* ($1001$ is a quadratic residue $\pmod {1111118111111}$)

Question

Given that $1111118111111$ is prime, determine whether $1001$ is a quadratic residue $\pmod {1111118111111}$.

Richard Ganaye · Accepted Answer

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

\begin{proof} Let $p = 1111118111111$. Since $1001 \equiv 1 \pmod 4$, 
\begin{align*}
\legendre{1001}{p} &= \legendre{p}{1001} = \legendre{1001 	imes 1110008103 + 8}{1001} =  \legendre {8}{1001} \
&= \legendre {2}{1001}^2  \legendre {2}{1001} =  \legendre {2}{1001}\
&= 1,
\end{align*}
because $1001 \equiv 1 \pmod 8$.
\end{proof}
Therefore $1001$ is a quadratic residue $\pmod {1111118111111}$.

\bigskip
Check : 
\begin{verbatim}
sage: is_prime(1111118111111)
True
sage: kronecker(1001,1111118111111)
1
\end{verbatim}

Exercise 3.2.18* ($1001$ is a quadratic residue $\pmod {1111118111111}$)

Answers

Comments

Exercise 3.2.18* ($1001$ is a quadratic residue $\pmod {1111118111111}$)

Answers

Comments

Add answer