Proof that the following multiplicative groups modulo m are cyclic

Question

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?

Answer 1

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

Answer 2

If you already know that $(\mathbb{Z}/m\mathbb{Z})^*$ is cyclic for $m=p^k$, then all that remains to prove is:

• $(\mathbb{Z}/m\mathbb{Z})^*$ is cyclic for $m=2p^k$, since the cases $m=1,2,4$ are very easy.

• $(\mathbb{Z}/m\mathbb{Z})^*$ is not cyclic for $m$ not of the form $m=1, 2, 4, p^k, 2p^k$.

These two facts come from the Chinese remainder theorem: $$ (\mathbb{Z}/m\mathbb{Z})^* \cong (\mathbb{Z}/p_1^{e_1}\mathbb{Z})^* \times \cdots \times (\mathbb{Z}/p_n^{e_n}\mathbb{Z})^* $$ when $m=p_1^{e_1} \cdots p_n^{e_n}$ is its factorization into primes.

The key observation for proving that $(\mathbb{Z}/m\mathbb{Z})^*$ is not cyclic for $m$ not of the form given is this:

Let $e = lcm(\phi(p_1^{e_1}), \ldots, \phi(p_n^{e_n}))$. Then $a^e=1$ for all $a \in (\mathbb{Z}/m\mathbb{Z})^*$.

which can be verified directly but also follows from

If $r,s$ are both even, then $C_r \times C_s$ is not cyclic.