2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ What is $QR_n$? $\endgroup$ – Jef L Mar 14 '15 at 15:46
1
$\begingroup$

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

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