Primitive root theorem

Statement

Let $n$ be an integer with $n \ge 2$. There is a primitive root modulo $n$ if and only if $n \in \{2, 4, p^k, 2p^k\}$. Here $p$ is an odd prime and $k$ is a positive integer.

Remarks

Equivalently, the group $(\mathbb{Z}/n\mathbb{Z})^\times$ is cyclic exactly for these $n$. The case $n = p$ is the existence of primitive roots modulo a prime. For example, there are primitive roots modulo $9$, $18$ and $25$, but not modulo $8$, $12$ or $15$.

History

Carl Friedrich Gauss gave the first proof. He defined primitive roots in his Disquisitiones Arithmeticae of 1801.

Explanations

L1 human

Modulo $12$, the residues coprime to $12$ are $1, 5, 7, 11$, and each of them squares to $1$. So no single residue generates all four, and there is no primitive root modulo $12$. The theorem lists exactly the moduli for which a generator exists.