Primitive root modulo n

Definition

Let $n$ be a positive integer. A primitive root modulo $n$ is an integer $g$ coprime to $n$ whose multiplicative order modulo $n$ is $\varphi(n)$, where $\varphi$ is Euler's totient function.

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

Explanations

L1 human

A primitive root is a number whose powers run through all the residues coprime to $n$ before they come back to $1$. Modulo $5$, the powers of $2$ are $2, 4, 3, 1$. So $2$ is a primitive root modulo $5$, but $4$ is not, since $4^2 \equiv 1$.