Primitive root modulo n (${\mathrm{ord}}_N(g)=\phi (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 Fibonacci primitive root modulo an odd prime $p$ is a primitive root modulo n $g$ satisfying $g^2\equiv g+1(\mathrm{mod}p)$. Its powers obey $g^{n+2}=g^{n+1}+g^n$, so the same multiplication that generates all nonzero residues also follows a Fibonacci recurrence.

For example, $3$ works modulo five: $3^2\equiv 3+1$ and its powers $1,3,4,2$ exhaust the nonzero residues. Solving the quadratic condition alone is insufficient; the multiplicative order must also equal $p-1$. Away from $p=5$, the quadratic has roots only when its discriminant five is a quadratic residue modulo $p$.

Let $p$ be an odd prime and $b$ a primitive root modulo $p$. Then $b$ is a primitive root modulo every prime power $p^m$ if and only if it is a primitive root modulo $p^2$. In that caseThe condition at $p^2$ says $b^{p-1}=1+pc$ with $p\nmid c$. The odd-prime case of the lifting-the-exponent lemma, obtained here by repeated use of the binomial theorem and then raising to an exponent not divisible by $p$, givesHere $v_p$ is the prime valuation. To see the induction step, the first term in $(1+p^{r}u{)}^p-1$ has prime valuation $r+1$, while every later term has strictly greater prime valuation when $p$ is odd and $p\nmid u$.

Any return $b^k\equiv 1(\mathrm{mod}{p}^m)$ must have $p-1\mid k$, by its order modulo $p$. Writing $k=(p-1)t$, the displayed valuation forces $p^{m-1}\mid t$, with equality giving a return. This proves the claimed multiplicative order. The reverse implication follows by taking $m=2$.

With the one-element unit group convention at $n=1$, a positive integer modulus admits a primitive root exactly whenwhere $p$ is an odd prime and $a\ge 1$.

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}\equiv 1(\mathrm{mod}{p}^2)$, thenThus 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\ge 3$ also has the four distinct roots $\pm 1$ and $\pm (1+2^{a-1})$. These cover every omitted case.

When a primitive root exists, their number is $\phi (\phi (n))$. If $g$ generates the unit group of size $m=\phi (n)$, its power $g^j$ has multiplicative order $m/\gcd (j,m)$, so exactly the coprime exponent classes generate. Here $\phi$ is Euler's totient function.