[Math] Prove that The product of a quadratic residue and a quadratic nonresidue of an odd prime p is a quadratic nonresidue.


Please check my proof.

I know this proof can be easier if use legendre symbol, but the problem does not allow to use it.

Suppose $a$ is quadratic residue
from Euler's criteria

$a^{(p-1)/2}\equiv 1 \pmod{p}$

and $b$ is quadratic nonresidue
It will be
$b^{(p-1)/2}\not\equiv 1 \pmod{p}$ or $b^{(p-1)/2}\equiv c \pmod{p}$ for some c

$(ab)^{(p-1)/2}\equiv c \pmod{p}$

$(ab)^{(p-1)/2}\not\equiv 1 \pmod{p}$
by congruence's property

If $a\equiv b \pmod{m}$ and $c\equiv d \pmod{m}$ then $ac\equiv bd \pmod{m}$
then the product of quadratic residue and quadratic nonresidue is quadratic nonresidue

Best Answer

Yes, this proof is correct, and indeed is the shortest proof (in my opinion).

Note that if $b^{(p-1)/2}\not\equiv1\pmod p$, then necessarily $b^{(p-1)/2}\equiv-1\pmod p$ (that is, we have to have $c=-1$). This is because $(b^{(p-1)/2})^2\equiv1\pmod p$ by Fermat's little theorem, and the only solutions to $x^2\equiv1\pmod p$ are $x\equiv\pm1\pmod p$.