Rigorous proof of how many solutions exist to $x^{2} \equiv 1 \mod pq$

Question

Let $p$ and $q$ be two distinct primes. I need to compute the number of solutions of the equation $x^{2}=1$ in $\mathbb{Z}_{pq}$, which, I assume, is equivalent to finding the number of solutions to $x^{2} \equiv 1 \mod pq$.

Now, I know there are quite a few questions asked on MSE that are similar to this one, but they have not been exactly the same, nor have their answers been of sufficient rigor for what I'm looking for.

For example, I tried to base a solution off this , although I'll admit that 1) I don't know what a "primitive root" is - we've never used that terminology in my class, and 2) I am not sure I entirely understand the proof that OP gives in her question.

There is another proof given in an answer to that question that is very simple, but I fear it is too simple and handwavey. i.e., the one that says that the Chinese Remainder Theorem allows us to solve $\begin{cases} m \equiv \pm x \mod p \\ m \equiv \pm x \mod q\end{cases}$.

I know that I am going to have to use the Chinese Remainder Theorem, and I intuitively have an idea that there should be 4 solutions, because there would be two, $\pm x$, for each of $p$ and $q$, but I don't know how to fit the pieces of the puzzle and write out a good, rigorous proof to show this.

Also, I've heard there can be zero solutions in this case. How does that happen?

Thanks for your time and patience.

Answer 1

The first thing you can use is the following (also known as the prime property). If $p | ab$, then $p|a$ or $p|b$.

Let us assume that $p>2$. Now consider the congruence $x^2 \equiv 1 \pmod{p}$. For it to have a solution, we want $p | (x-1)(x+1)$. By the prime property (mentioned above) we have that $p|x-1$ or $p|x+1$. However $p$ cannot divide both, because if it did then $p|(x+1)-(x-1)=2$ which is not possible as $p$ is an odd prime. Thus we have only two solutions namely $x \equiv \pm 1 \pmod{p}$.

Similarly we have $x^2 \equiv 1 \pmod{q}$ has two solutions $x \equiv \pm 1 \pmod{q}$.

Now we can combine these solutions to form $4$ systems as follows: \begin{align*} x & \equiv 1 \pmod{p} & x & \equiv -1 \pmod{p} & x &\equiv -1 \pmod{p} & x & \equiv 1 \pmod{p}\\ x & \equiv 1 \pmod{q} & x & \equiv -1 \pmod{q} & x &\equiv 1 \pmod{q} & x & \equiv -1 \pmod{q}. \end{align*} The first two systems have solutions $x \equiv \pm1 \pmod{pq}$. Now we can solve the other two systems to get two more solutions. In all $4$ solutions (when $p$ and $q$ are odd distinct primes).

Answer 2

The CRT is indeed the key. $x^2 - 1 = (x+1)(x-1)$. $\mathbb Z_p$ for $p$ prime is a field, so for this product to be $0$ in $\mathbb Z_p$ one of the two factors must be $0$. Thus the solutions to $x^2 = 1$ in $\mathbb Z_p$ are $x = \pm 1$. And then the CRT says for any $a \in \mathbb Z_p$ and $b \in \mathbb Z_q$, there is exactly one $x \in \mathbb Z_{pq}$ with $x \equiv a \mod p$ and $x \equiv b \mod q$. So if $p$ and $q$ are odd primes, you get four solutions, one corresponding to $+1 \mod p,\; +1 \mod q$, one for $+1, -1$, etc.

On the other hand, if $p$ or $q$ is $2$, you get only two solutions because $+1$ and $-1$ are the same mod $2$.