 Primitive root modulo n

For an integer modulus $N\ge 2$, a primitive root is a unit $g$ whose multiplicative order is $\phi (N)$. Its powers enumerate the entire unit group $U(N)$, so a primitive root exists exactly when this group is a cyclic group.

Modulo seven, successive powers of three give $3,2,6,4,5,1$, reaching all six units. The element two instead has powers $2,4,1$ and multiplicative order three, so it is not a primitive root.^[ref]

Existence depends on $N$. Modulo eight, every unit is represented by an odd integer and has square one, since $(2k+1{)}^2-1=4k(k+1)$ is divisible by eight. No such element can generate a group of four units. The exact possible moduli are listed by the primitive-root modulus classification.

A primitive root modulo \( n \) is an integer \( g \) such that its powers generate all the integers coprime to \( n \) up to \( n \).