Number of solutions of $x^2=1$ in $\mathbb{Z}/n\mathbb{Z}$

Question

Next is what I have worked out to the moment.

$1$ and $-1$ are roots for all $n$.

$x \in \mathbb{Z}/n\mathbb{Z},\ $ $x^2\equiv1 \Leftrightarrow (x-1)(x+1)\equiv0 \Leftrightarrow \exists k \in \mathbb{Z}/n\mathbb{Z}: k(k+2)\equiv0 $. But how can it be applied to find other roots?

Answer 1

(I'd have to check the details in the following but it provides some rough ideas.)

Write $n = \prod_i p_i^{\nu_i}$ and use the Chinese remainder theorem to obtain a system of equations

$$ x^2 \equiv 1 \pmod{p_i^{\nu_i}}$$ Of course, for every $p_i$, $x=\pm 1$ provides a solution. Based on some quick calculations, I think that:

• If $p_i>2$, these are the only solutions.
• If $p_i=2$ and $\nu_2 \geq 3$, then there are 4 solutions.
• If $p_i=2$ and $\nu_2 = 2$, then $x=\pm 1$ are solutions.
• If $p_i=2$ and $\nu_2 = 1$, there is $1$ solution, because $+1 = -1$.

To confirm this: investigate when a prime power can divide two numbers that differ by $2$, i.e when $p_i^{\nu_i} \mid (x+1)(x-1)$.

We may then use the Chinese remainder theorem to reassemble the solutions to find solutions mod $n$: each combination of solutions modulo the prime-powers will uniquely determine a solution mod $n$.

So the number of solutions is (where $\omega(n)$ is the number of distinct prime factors of $n$):

• $2^{\omega(n)}$ if $n$ is odd or $\nu_2 = 2$.
• $2^{\omega(n)+1}$ if $\nu_2 \geq 3$
• $2^{\omega(n)-1}$ if $\nu_2 = 1$

---

A proof of the above can be based on theorem 4.19 and 4.20 in Basic Algebra vol 1, by N. Jacobson, discussing the structure of $U_{p^\nu}$, this is the group of units in $\mathbb Z/p^\nu \mathbb Z$: it is cyclic if $p>3$, $p^\nu=2$ or $p^\nu=4$ and isomorphic to $C_2\times C_{2^{\nu-2}}$ if $p=2$ and $\nu\geq 3$.