Suppose $n = pq$ with $p$ and $q$ distinct odd primes.
Suppose that $\gcd(a,pq)=1$. Prove that if the equation $x^{2} \equiv a\pmod n$ has any solutions, then it has four solutions.
Proof: Suppose $n = pq$ with $p$ and $q$ distinct odd primes and that gcd($a,pq$) = 1. Let us have the equation $x^{2} \equiv a\pmod n$. Then, $x^{2} \equiv a$ (mod $pq$), $p \not = q$. By definition, we can separate the equation into two equations such that $y^{2} \equiv a \equiv b$ (mod $p$) and $z^{2} \equiv a \equiv c$ (mod $q$). Let $g_{p}$ be a primitive root modulo $p$ and $g_{q}$ be a primitive root modulo $q$. Then, $b$ is equal to some power of $g_{p}$ and $c$ is equal to some power of $g_{q}$. With the fact that $b$ has a square root modulo $p$ (i.e. $r^{2} \equiv b$(mod $\ p)$) and $c$ has a square root modulo $q$ (i.e. $t^{2} \equiv c$(mod $\ q)$), there is an even power of $g_{p}$ and of $g_{q}$ such that $b = g_{p}^{2k_{1}}$(mod $\ p)$ and $c = g_{q}^{2k_{2}}$(mod $\ q)$ for some $k_{1}, k_{2} \in Z$. By computing, we have the following:
$r^{2} \equiv b$(mod $\ p)$
$\equiv b^{(p + 1) / 2}($mod $\ p)$
$\equiv (g_{p}^{2k_{1}})^{(p + 1) / 2}($mod $\ p)$
$\equiv (g_{p}^{p + 1})^{k_{1}}($mod $\ p)$
$\equiv g_{p}^{2k_{1} + (p – 1)k_{1}}($mod $\ p)$
$\equiv b \cdot g_{p}^{(p – 1)k_{1}}($mod $\ p)$
$\equiv b$
and
$t^{2} \equiv c$(mod $\ q)$
$\equiv c^{(q + 1) / 2}($mod $\ q)$
$\equiv (g_{q}^{2k_{2}})^{(q + 1) / 2}($mod $\ q)$
$\equiv (g_{q}^{q + 1})^{k_{2}}($mod $\ q)$
$\equiv g_{q}^{2k_{2} + (q – 1)k_{2}}($mod $\ q)$
$\equiv c \cdot g_{q}^{(q – 1)k_{2}}($mod $\ q)$
$\equiv c$
Hence, $r$ is a square root of a modulo $p$ and $t$ is a square root of a modulo $q$, which means there are two solutions for each $p$ and $q$. Since $p \not = q \in \mathbb{Z}_{n}$, we have isomorphism such that $\mathbb{Z}_{n} \simeq \mathbb{Z}_{p} \cdot \mathbb{Z}_{q}$. Therefore, if the equation $x^{2} \equiv a$ (mod $n$) has any solutions, it must have four solutions. $\blacklozenge$
What do you think about the proof I wrote?
Best Answer
You can use the Chinese Remainder theorem to produce the result. Say $x$ is your square root of $a$. Then we note that we can find $x_2, x_3, x_4$ all distinct which also square to $a$. How?
Well, we note that the CRT allows us to solve
$$\begin{cases} m\equiv \pm x\mod p \\ m\equiv\pm x\mod q\end{cases}$$
Here we use the existence of $x$ to setup the system. But then we have $2$ choices for the sign of $x$ modulo $p$ and two (independent) choices for the sign of $x$ modulo $q$. When we have $(+,+)$ this is our original $x$, or $x_1$. Then we can denote the other solutions based on their reductions to the smaller moduli, $(+,-)\longleftrightarrow x_2$, $(-,+)\longleftrightarrow x_3$, $(-,-)\longleftrightarrow x_4$.
Since these are inequivalent modulo $p$ or $q$, we have that they are inequivalent modulo $pq$, hence all four give rise to distinct square roots modulo $pq$, as desired.