How to show that a the group $( \mathbb{Z} / n \mathbb{Z} )^* $ has elements of order $2$ Let   $ n \in \mathbb{N} $ have prime factorization  $ n = 2^e p_1^{e_1}...p_r^{e_r}, $
with  $ 0 \leq e $ and pairwise odd primes $ p_1,...,p_r $ 
and $ 1 \leq e_1,...,e_r. $
How do you prove that the group $ ( \mathbb{Z} / n \mathbb{Z})^* $ then has
$ \left\{ \begin{array} {ll} 2^r-1, \text{ if }    e=0  \lor  1 \\ 2^{r+1} -1 , \text{ if }  e=2 \\ 2^{r+2} -1 , \text{ if }3 \leq e \end{array} \right.$
elements of order $2$?
Appreciate any help, because I am not really sure how to prove that !
 A: By the Chinese remainder theorem, solutions of $a^2\equiv1\bmod n$ 
correspond to solutions of $a^2\equiv1 \bmod 2^e$, $a^2\equiv1 \bmod p_1^{e_1},\dots,$ and  $a^2\equiv1 \bmod p_r^{e_r}$.


*

*If $e=0$ or $1$, there is one solution to $a^2\equiv1\bmod2^e:  \;a\equiv1 \bmod 2^e$.

*If $e=2$, there are $\color{blue}{2}$ solutions to $a^2\equiv1\bmod2^e:\;  a\equiv1$ or $-1\bmod 2^e$.

*If $e\ge3$, there are $\color{brown}4$ solutions to $a^2\equiv1\bmod 2^e:\;  a\equiv\pm1$ or $2^{e-1}\pm1\bmod 2^e$.

*There are two solutions to $a^2\equiv1\mod p_i^{e_i}:\;  a\equiv1$ or $-1\bmod p_i^{e^i}$.
Therefore, putting these together by the Chinese remainder theorem,
there are $2^r$ solutions to $a^2\equiv1\bmod n$ if $e=0$ or $1$,
$\color{blue}2\times2^r=2^{r+1}$ solutions to $a^2\equiv1\bmod n$ if $e=2$,
and $\color{brown}4\times2^r=2^{r+2}$ solutions to $a^2\equiv1\bmod n$ if $e\ge3$.
In each case, one of the solutions is $a\equiv1\bmod n$, which has order $1$, and the others have order $2$.
