4
$\begingroup$

Let $x,y$ be integers and $y$ be a (nonzero) quadratic residue modulo $p$ ($p$ is a prime). Prove that $xy$ is a quadratic residue modulo $p$ if and only if $x$ is a quadratic residue modulo $p$.

If $x$ is a quadratic residue modulo $p$, then the result is trivial. How do we prove the other direction?

$\endgroup$
  • $\begingroup$ I suppose $y$ is quadratic residue mod $\color{red}p$. The Legendre symbol is mutiplicative. $\endgroup$ – Bernard Aug 17 '16 at 22:01
  • $\begingroup$ @Bernard Yes, typo. $\endgroup$ – Puzzled417 Aug 17 '16 at 22:03
  • $\begingroup$ If $y$ is a quadratic residue then it's easy to show that $y^{-1}$ is a quadratic residue. So both directions are trivial. $\endgroup$ – Erick Wong Aug 29 '16 at 0:52
13
$\begingroup$

Suppose that $xy$ is a QR of $p$. Then $xy\equiv z^2\pmod{p}$ for some $z$. Since $y$ is a QR of $p$, we have $y\equiv w^2\pmod{p}$ for some $w$.

Thus $xw^2\equiv z^2\pmod{p}$. Multiply both sides by $(w^{-1})^2$. We get that $$x\equiv (w^{-1}z)^2\pmod{p}.$$

$\endgroup$
2
$\begingroup$

The quadratic residues are the members of the group G of squares. If xy and x are in G so is y, and of course by definition of a group if x and y are in G so is xy.

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