= Primitive root modulo n
{title2=$\operatorname{ord}_N(g)=\varphi(N)$}
{wiki}
= Primitive root
{synonym}
For an <integer modulus> $N\geq2$, a <primitive root> is a <unit> $g$ whose <multiplicative order> is $\varphi(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>.<Orders of Units in Modular Arithmetic by Keith Conrad>[§1, Example 1.1 and Definition 1.3, printed p. 1: orders of units modulo seven]{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>.
Back to article page
