Primitive root modulo n

Remarks

Equivalently, $g$ is a primitive root modulo $n$ when the powers $g, g^2, \dots, g^{\varphi(n)}$ represent all the residue classes coprime to $n$. So a primitive root exists exactly when the group $(\mathbb{Z}/n\mathbb{Z})^\times$ is cyclic, and then $\overline{g}$ generates this group. For example, $3$ is a primitive root modulo $7$: its powers are $3, 2, 6, 4, 5, 1$ modulo $7$. There is no primitive root modulo $8$: each odd $a$ satisfies $a^2 \equiv 1 \pmod 8$, but $\varphi(8) = 4$.