In the Wikipedia page about the multiplicative groups modulo $m$, the following claim is made:
The group $(\mathbb{Z}/m\mathbb{Z})^*$ is cyclic if and only if $m=1, 2, 4, p^k$ or $2p^k$, where $p$ is an odd prime and $k > 0$.
No proof is provided. Could someone provide a proof of the above statement? Thanks
I already have a proof that if $m$ is an odd prime, then $(\mathbb{Z}/m^r\mathbb{Z})^*$ is cyclic if $m$ is an odd prime. assuming this, how do I prove the above?
Best Answer
I'll sketch the case of $n=p^k\ (k>1)$, taking for granted that $(\mathbf Z/p\mathbf Z)^\times$ is cyclic.
Note that $\bigl\lvert\mathbf Z/p^k\mathbf Z\bigr\rvert=\varphi(p^k)=p^{k-1}(p-1)$.
One shows first, using the binomial formula that, if $p$ is an odd prime, $$(1+p)^{p^k}=1+a_k p^{k+1},\quad \gcd(a_k, p)=1$$ From this fact we deduce $1+p$ has order $\;p^{k-1}\bmod p^k$.
Second, the multiplicative group of $\mathbf Z/p\mathbf Z$ is cyclic, of order $p-1$, hence there exists an integer $a$, $1<a<p$ of order $p-1\bmod p$, hence its order modulo $p^k$ is a multiple of $p-1$, so that one of its powers $b$ has order $p-1$.
Third, $b(1+p)$ has order $\operatorname{lcm}(p-1,p^{k-1})$, and as $p-1$ and $p^{k-1}$ are coprime, this order is equal to $(p-1)p^{k-1}$. Thus $(\mathbf Z/p^k\mathbf Z)^\times$ is generated by the class of $\;b(1+p)\bmod p^k$.