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.

  • 1
    What is $QR_n$? – Jef L Mar 14 '15 at 15:46
up vote 1 down vote accepted

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

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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