When is the group of units in $\mathbb{Z}_n$ cyclic? [duplicate]

Let $U_n$ denote the group of units in $\mathbb{Z}_n$ with multiplication modulo $n$. It is easy to show that this is a group. My question is how to characterize the $n$ for which it is cyclic. Since the multiplicative group of a finite field is cyclic so for all $n$ prime, it is cyclic. However I believe that for certain composite $n$ it is also cyclic.

Searching through past posts turned up this, where there was an answer containing the sentence "In number-theoretic situations there are coherent things that can be said, and/but in general I think nothing decisive can be said."

What are those number theoretic situations?

Thanks

Solution 1:

$U_n$ is cyclic if and only if $n = 1$, $n = 2$, $n = 4$, $n = p^k$ or $n = 2p^k$ where $p$ is any odd prime.

Proving this requires some work, but proofs can be found in many undergraduate textbooks on number theory and abstract algebra.

The basic idea is this. If an integer $n > 1$ has prime factorization $n = p_1^{a_1} \ldots p_t^{a_t}$, then $U_n \cong U_{p_1^{a_1}} \times \cdots \times U_{p_t^{a_t}}$ by the Chinese remainder theorem. Thus to describe the structure of $U_n$, it suffices to consider the case where $n$ is a power of a prime. It is possible to show that $U_{2^k} \cong \mathbb{Z}_2 \times \mathbb{Z}_{2^{k-2}}$ for $k \geq 3$. Also, $U_{p^k}$ is cyclic for any odd prime $p$ and $k \geq 1$. When you have these results, finding the $n$ for which $U_n$ is cyclic is not too difficult.

Solution 2:

The group is cyclic when $n$ is a power of an odd prime, or twice a power of an odd prime, or $1$, $2$ or $4$. That's all.

Usually this is put in number-theoretic language: there is a primitive root modulo $n$ precisely under the conditions given above. These results are originally due to Gauss (Disquisitiones Arithmeticae).