How do I see that $a^2 \equiv 1 \mod{( p \cdot q)}$ has four incongruent solutions?

Question

How do I see that $a^2 \equiv 1 \mod{( p \cdot q)}$ has four congruent solutions?

Studying cryptography, I've seen that given $p$ and $q$ are primes, the equation above should have 4 incongruent solutions.

I see immediately, that $\pm 1$ are solutions, but I don't know how to prove existence of other two.

Also, are there circumstances for which $a^2 \equiv x \mod{( p \cdot q)}$ has four incongruent solutions, e.g. does it always hold for $\gcd({x, p\cdot q}) = 1$?

Answer 1

Here $p, q$ are two distinct odd primes.

If $p = 3$, $q = 5$, for instance, you get the four solutions $a = 1, -1, 4, -4$.

In general the four solutions modulo $pq$ will be the solutions of the four systems \begin{cases} a \equiv \pm 1 \pmod{p}\\ a \equiv \pm 1 \pmod{q}\\ \end{cases}

With the same approach, $a^{2} \equiv x \pmod{p q}$ has four incongruent solutions if and only if $x$ is a non-zero square modulo $p q$.

Answer 2

It doesn't necessarily. If $p = 2$ and $q=3$, then

$$0^2 \equiv 0 \pmod 6$$ $$1^2 \equiv 1 \pmod 6$$ $$2^2 \equiv 4 \pmod 6$$ $$3^2 \equiv 3 \pmod 6$$ $$4^2 \equiv 4 \pmod 6$$ $$5^2 \equiv 1 \pmod 6$$

and only two are solutions.