7
$\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$
3
  • $\begingroup$ I suppose $y$ is quadratic residue mod $\color{red}p$. The Legendre symbol is mutiplicative. $\endgroup$
    – Bernard
    Aug 17, 2016 at 22:01
  • $\begingroup$ @Bernard Yes, typo. $\endgroup$
    – Puzzled417
    Aug 17, 2016 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, 2016 at 0:52

2 Answers 2

22
$\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$
1
  • 1
    $\begingroup$ It has been 7 years since we saw you, sir. I hope you are doing well. $\endgroup$
    – pie
    Nov 22, 2023 at 15:25
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$
1
  • $\begingroup$ This feels circular. The assertion that the squares form a subgroup is essentially the same as what the question is asking. $\endgroup$
    – Erick Wong
    Jul 4, 2021 at 21:16

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .