Number of solutions of $x^2=1$ in $\mathbb{Z}/n\mathbb{Z}$ 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?

(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$.
