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

This question already has an answer here:

  • For what $n$ is $U_n$ cyclic?

    3 answers

Solutions Collecting From Web of "When is the group of units in $\mathbb{Z}_n$ cyclic?"

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

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