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

• Gauss showed that $U_n$ is cyclic if and only if $n=2,4,p^k,$ or $2p^k$ for $p$ an odd prime, $k$ a natural number. – Jared Apr 26 '13 at 17:17
• en.wikipedia.org/wiki/… – Alex Provost Apr 26 '13 at 17:19
• Most certainly a duplicate. – lhf Apr 26 '13 at 18:17
• @Lhf The question is certainly not a duplicate of the linked question, since the author is asking additionally a more general question, namely "What are those number theoretic situations?" (where the unit group is cyclic). This is an interesting question that is not addressed at all in the proposed duplicate. – Math Gems Apr 26 '13 at 19:15
• @Shahab: Is this statement is correct "the multiplicative group of a finite field is cyclic so for all n prime, it is cyclic." – Aria Aug 13 '14 at 7:11

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

• Just wondering: is the empty group considered cyclic? – Julien Apr 26 '13 at 20:03
• The «empty group» is not a group. – Mariano Suárez-Álvarez Apr 26 '13 at 20:18
• Groups are always nonempty since they contain the identity. – Mikko Korhonen Apr 26 '13 at 20:35

The group is cyclic when $$n$$ is a power of a prime, or twice a power of a prime, or $$1$$. 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).