0
$\begingroup$

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 then

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

$(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

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.