Quadratic residue, bijective mapping?

Question

Let $p$ and $q$ be two odd primes such that $p \equiv q \equiv 3 \pmod 4$, and let $n=pq$.

Seems that $f:\text{QR}_n\to \text{QR}_n$, $f(x) \equiv x^2$

is a bijection. Have trouble as to why is it so.

Answer 1

We assume that $p$ and $q$ are distinct primes of the form $4k+3$, and that $n=pq$. It is clear that for any $x$ relatively prime to $n$, the number $x^2$ is a QR of $n$. So to show that the map $f$ is a bijection, it is enough to show that if $x$ and $y$ are QR of $n$ and distinct modulo $n$, then $f(x)\not\equiv f(y)\pmod{n}$.

If $x$ and $y$ are distinct modulo $n$, then they are distinct modulo at least one of $p$ and $q$, say $p$. We will show that $f(x)\not\equiv f(y)\pmod{p}$.

Suppose to the contrary that $x\not\equiv y\pmod{p}$ and $x^2\equiv y^2\pmod{p}$. Let $z$ be the modular inverse of $y$. Then from $x^2\equiv y^2\pmod{p}$ we conclude that $(xz)^2\equiv 1\pmod{p}$. It follows that $xz\equiv \pm 1\pmod{p}$. If $xz\equiv 1\pmod{p}$, then we have contradicted the fact that $x$ and $y$ are distinct modulo $p$. So $xz\equiv -1\pmod{p}$. This is impossible, since $x$ and $z$ are QR of $p$, and therefore so is $xz$. But since $p$ is of the form $4k+3$, $-1$ cannot be a QR of $p$.