= Primitive-root modulus classification
With the one-element <unit group> convention at $n=1$, a positive <integer modulus> admits a <primitive root> exactly when
$$
n=1,\ 2,\ 4,\ p^a\ \text{or}\ 2p^a,
$$
where $p$ is an <odd prime> and $a\geq1$.
For existence, the <finite subgroup of a field multiplicative group is cyclic> theorem supplies a <primitive root> $g$ <modulo> $p$. At least one of $g$ and $g+p$ satisfies the <primitive-root lifting criterion>: if $g^{p-1}\equiv1\pmod{p^2}$, then
$$
(g+p)^{p-1}\equiv g^{p-1}+(p-1)g^{p-2}p\not\equiv1\pmod{p^2}.
$$
Thus <lifting a primitive root to odd prime powers> gives every $p^a$. The <Chinese remainder theorem for unit groups> identifies $U(2p^a)$ with $U(p^a)$ because $U(2)$ is trivial. The moduli two and four are checked directly.
For exclusion, a <cyclic group> has at most two solutions of $x^2=1$. If a modulus has two distinct odd <prime factors>, or is divisible by both four and an odd <prime number>, independent sign choices under the <Chinese remainder theorem> give at least four such <units>. A pure power $2^a$ with $a\geq3$ also has the four distinct roots $\pm1$ and $\pm(1+2^{a-1})$. These cover every omitted case.
When a <primitive root> exists, their number is $\varphi(\varphi(n))$. If $g$ generates the <unit group> of size $m=\varphi(n)$, its power $g^j$ has <multiplicative order> $m/\gcd(j,m)$, so exactly the <coprime> exponent classes generate. Here $\varphi$ is <Euler's totient function>.
Back to article page