Proving that the multiplicative group modulo $2^r$ are cyclic iff $r<3$

Question

No idea how to start, can someone give me a hint?

Show that $(\mathbb{Z}/2^r\mathbb{Z})^*$ is a cyclic group if and only if $r<3$.

Answer 1

Hint: It is easy to verify directly that the group is cyclic if $r=0$, $1$, or $2$.

To show the group is not cyclic if $r\ge 3$, note that in a cyclic group the equation $x^2=1$ has at most $2$ solutions. But if $r\ge 3$, then the congruence $x^2\equiv 1\pmod{2^r}$ has, beside the two obvious solutions, solutions $x\equiv 2^{r-1}\pm 1\pmod{2^r}$.

Added: We show that if a finite group $G$ is cyclic, then the equation $x^2=1$, where $1$ is the identity element, has at most two solutions.

Let $G$ have $n$ elements, and let $g$ be a generator of $G$. So every element of $G$ is of the shape $g^k$, where $1\le k\le n$, and $g^n=1$.

Suppose that $x^2=1$. Then $x=g^t$ for some $r$ between $1$ and $n$, and $g^{2t}=1$. It follows that $2t$ divides $n$. If $t\ne n$, then $2\le 2t\lt 2n$. Thus we must have $2t=n$. We conclude that there is at most one solution of $x^2=1$ other than the trivial solution $x=1$.