Chinese Remainder Theorem: four square roots of 1 modulo N

Question

Given an odd composite number $N$, where $N$ is not a prime power, I read the following in a Wikipedia article:

As a consequence of the Chinese remainder theorem, the number $1$ has at least four distinct square roots modulo $N$, two of them being $1$ and $-1$.

The square roots of $1$ and $-1$ are obvious to me. What I don't understand is why there are necessarily two others.

Can anyone prove how this result follows from the Chinese remainder theorem?

Answer 1

This follows very simply from the observation that if you have two coprime moduli, $p$ and $q$, then $$\begin{cases} x\equiv a \bmod p \\ x\equiv a \bmod q \\ \end{cases} \qquad \implies x\equiv a \bmod pq $$ as a special case of the CRT. (I would like to write the paired equivalence as $x\underset{(p,q)}\equiv (a,a)$)

Then apply this here with $$\begin{cases} x^2\equiv 1 \bmod p \\ x^2\equiv 1 \bmod q \\ \end{cases} \qquad \implies x^2\equiv 1 \bmod pq $$ ... or $x^2\underset{(p,q)}\equiv (1,1)\implies x^2= 1 \bmod pq$

Then with $p,q>2$ (so that ${-}1{\not\equiv}1$), we can see that $x^2\underset{(p,q)}\equiv (1,1)$ will hold for each of $x\underset{(p,q)}\equiv \{(1,1),$ $(1,-1),(-1,1),$ $(-1,-1)\}$. These will each produce different roots of $1\bmod pq$ with the final values of $x\bmod pq$ determined through the CRT

---

As an example of how this works out, $21\underset{(5,11)}\equiv (1,-1)$ so $21^2\underset{(5,11)}\equiv (1,1)$ and thus $21^2\equiv 1 \bmod 55$.

Answer 2

If $N$ is divisible by two distinct odd primes (say $p, q$), besides $1, -1$, you can also choose $i$ such that $i \equiv 1 \mod p^{\nu_p(N)}, i \equiv -1 \mod q^{\nu_q(N)}, i \equiv 0 \mod \frac{n}{p^{\nu_p(N)}q^{\nu_q(N)}}$ and $j$ such that $j i \equiv -1 \mod p^{\nu_p(N)}, i \equiv 1 \mod q^{\nu_q(N)}, i \equiv 0 \mod \frac{n}{p^{\nu_p(n)}q^{\nu_q(N)}}$.

In general if $N$ is divisible by atleast $m$ odd primes, then there are exactly $2^m$ numbers whose square is congruent to $1$ modulo $N$.

Here $\nu_p(m)$ denotes the highest power of $p$ dividing $m$ (for example, $\nu_3(27) = 3$, $\nu_3(18) = 2$, $\nu_3(10) = 0$)

Answer 3

Let $N = mn$ with $mn$ relatively prime and both odd.

Then among the equivalence classes $\mod N$:

by CRT for each of the following systems of equation there is exactly one solution:

• $x \equiv 1 \mod m$ and $x\equiv 1 \mod m$. (In this case $x \equiv 1 \mod mn$).

• $y \equiv 1 \mod m$ and $y \equiv -1 \mod m$.

• $w \equiv -1 \mod m$ and $w\equiv 1\mod m$

• $u \equiv -1\mod m$ and $w\equiv -1 \mod m$.(this is $u \equiv -1 \mod mn$).

These are four distinct values $\mod mn$.

Now all four of these values have the properties that:

• $x^2 \equiv y^2 \equiv z^2 \equiv u^2 \equiv 1 \mod m$ and $x^2 \equiv y^2 \equiv z^2 \equiv u^2 \equiv 1 \mod n$.

By CRT there is exactly one solution $\mod mn$ to that:

$x^2 \equiv y^2\equiv z^2 \equiv u^2 \equiv 1 \mod mn$.

Answer 4

If $f:\mathbb Z_N \to \mathbb Z_{p_1^{\alpha_1}} \times Z_{p_2^{\alpha_2}} \times \cdots \times Z_{p_n^{\alpha_n}}$

where $N = p_1^{\alpha_1} \times p_1^{\alpha_1} \times \cdots \times p_n^{\alpha_n}$

is a group isomorphism (via the CRT), then every number of the form

$$f^{-1}(\pm 1, \pm 1, \dots, \pm 1)$$

is a square root of $1$ in $\mathbb Z_N$.

added 9/3/2022

Viewed from the other direction.

If $f: \mathbb Z_{p_1^{\alpha_1}} \times Z_{p_2^{\alpha_2}} \times \cdots \times Z_{p_n^{\alpha_n}} \to \mathbb Z_N$

is a group isomorphism (via the CRT), then every number of the form

$$f(\pm 1, \pm 1, \dots, \pm 1)$$

is a square root of $1$ in $\mathbb Z_N$.

For example, the map $f:Z_3 \times Z_5 \times Z_7 \to Z_{105}$ defined by $f(x,y,z) = 70x + 21y + 15z \pmod{105}$ is a group isomorphism. We get $$f( 1, 1, 1) \equiv 1 \pmod{105}$$ $$f( 1, 1,-1) \equiv 76 \pmod{105}$$ $$f( 1,-1, 1) \equiv 64 \pmod{105}$$ $$f( 1,-1,-1) \equiv 34 \pmod{105}$$ $$f(-1, 1, 1) \equiv 71 \pmod{105}$$ $$f(-1, 1,-1) \equiv 41 \pmod{105}$$ $$f(-1,-1, 1) \equiv 29 \pmod{105}$$ $$f(-1,-1,-1) \equiv 104 \pmod{105}$$

and $ 1^2 \equiv 76^2 \equiv 64^2 \equiv 34^2 \equiv 71^2 \equiv 41^2 \equiv 29^2 \equiv 104^2 \pmod {105}$