Exercise 3.21

Proof. Let $n=2^{a_0}{p}_1^{a_1}\cdots p_k^{a_k}$ be the decomposition in prime factors of $n>1$ ( $p_0=2<p_1<\cdots <p_k,a_0\ge 0,a_i>0,1\le i\le k$). Let $N$ be the number of solutions of $x^2\equiv 1(\mathit{mod}n)$, and $N_i$ the number of solutions of $x^2\equiv 1(\mathit{mod}{p}_i^{a_i}),i=0,1,\dots k$. From Ex.3.18, we know that $N=N_0{N}_1\cdots N_k$, where (Ex. 3.19), $N_i=2,i=1,2,\dots ,k$, and (Ex.3.20), $N_0=1$ if $a_0=1$ (or $a_0=0$), $N_0=2$ if $a_0=2$, $N_0=4$ if $a_0\ge 3$.

Conclusion : the number of solutions of $x^2\equiv 1(\mathit{mod}n)$, where $n=2^{a_0}{p}_1^{a_1}\cdots p_k^{a_k}$, is