$xy$ is a quadratic residue mod $p$ iff $x$ is a quadratic residue mod $p$, where $y$ be a (nonzero) quadratic residue mod $p$

1k Views Asked by At

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?

2

There are 2 best solutions below

1
On

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

1
On

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.