Exercise 3.1.9 (Product of nonresidues)

Question

Let $p$ be a prime, and let $(a,p) = (b,p) = 1$. Prove that if $x^2 \equiv a \pmod p$ and $x^2 \equiv b \pmod p$ are not solvable, then $x^2 \equiv ab \pmod p$ is solvable.

Richard Ganaye · Accepted Answer

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

\begin{proof}   Since $x^2 \equiv a \pmod p$ and $x^2 \equiv b \pmod p$ are not solvable, where $p 
mid a, \ p 
mid b$, $a,b$ are quadratic nonresidues, thus $\legendre{a}{p} = \legendre{b}{p} = -1$. Therefore
$$\legendre{ab}{p} = \legendre{a}{p}\legendre{b}{p} = (-1) \cdot (-1) = 1$$
(and $p 
mid ab$).
Therefore $x^2 \equiv ab \pmod p$ is solvable.

(This shows that the product of two quadratic nonresidues modulo $p$ is a quadratic residue modulo $p$.)
\end{proof}

Exercise 3.1.9 (Product of nonresidues)

Answers

Comments

Exercise 3.1.9 (Product of nonresidues)

Answers

Comments

Add answer