The Order of an Element and Primitive Roots

We use the division algorithm, the technique of writing $k = qd + r$ with $0 \le r < d$. ($\Leftarrow$) Suppose $d \mid k$, say $k = md$ for some positive integer $m$. Since $a^d \equiv 1 \pmod n$ by definition of order, raising both sides to the $m$-th power gives

($\Rightarrow$) Suppose $a^k \equiv 1 \pmod n$. By the division algorithm applied to $k$ and $d$, write

for unique integers $q, r$. Then

More carefully (to avoid negative exponents before establishing invertibility, though $a$ is already a unit mod $n$ since $\gcd(a,n)=1$): from $a^k = a^{qd} \cdot a^r$ we get

using $a^k \equiv 1$ and $a^d \equiv 1$, and the fact that $a$ (hence $a^d$) is invertible mod $n$ because $\gcd(a,n) = 1$ (this is the standard fact that invertibility mod $n$ is equivalent to being coprime to $n$, established via Modular Inverses and Bézout's identity). So $a^r \equiv 1 \pmod n$ with $0 \le r < d$. But $d$ is by definition the least positive integer with $a^d \equiv 1 \pmod n$. If $r$ were a positive integer less than $d$ with $a^r \equiv 1$, this would contradict minimality of $d$. Hence we must have $r = 0$ (the only non-positive option in range, since $r \geq 0$). Therefore $k = qd$, i.e. $d \mid k$. Finally, by Euler's Theorem, $a^{\varphi(n)} \equiv 1 \pmod n$ (valid since $\gcd(a,n)=1$). Applying the equivalence just proved with $k = \varphi(n)$ gives $d \mid \varphi(n)$, i.e. $\operatorname{ord}_n(a) \mid \varphi(n)$. $\blacksquare$

We induct on $m$, using the factor theorem mod $p$ together with the fact that $\mathbb{Z}/p\mathbb{Z}$ has no zero divisors (a direct consequence of $p$ being prime: if $p \mid uv$ then $p \mid u$ or $p \mid v$, Euclid's lemma). Base case $m = 1$: $f(x) = c_1 x + c_0$ with $c_1 \not\equiv 0$. The congruence $c_1 x \equiv -c_0 \pmod p$ has a unique solution mod $p$ since $c_1$ is invertible mod $p$ (as $p \nmid c_1$, via Bézout). So there is exactly $1 \le 1$ solution. Inductive step: Suppose the claim holds for all degrees less than $m$. If $f(x) \equiv 0 \pmod p$ has no solutions, the bound $0 \le m$ holds trivially. Otherwise let $a$ be one solution: $f(a) \equiv 0 \pmod p$. Perform polynomial division with remainder over $\mathbb{Z}$: since the leading coefficient of $(x - a)$ is $1$ (a unit), we can write

for a polynomial $g$ of degree $m - 1$ with integer coefficients and a constant $r \in \mathbb{Z}$ (ordinary polynomial division, valid over any commutative ring when dividing by a monic polynomial). Substituting $x = a$: $f(a) = r$, so $r \equiv 0 \pmod p$ since $f(a) \equiv 0$. Hence

as polynomials, i.e. coefficientwise mod $p$ (subtracting the two sides gives the zero polynomial mod $p$, since $r \equiv 0$). The leading coefficient of $g$ equals the leading coefficient of $f$, namely $c_m \not\equiv 0 \pmod p$, so $g$ has degree exactly $m - 1$ as a polynomial mod $p$. By the inductive hypothesis, $g(x) \equiv 0 \pmod p$ has at most $m - 1$ solutions mod $p$. Now suppose $b$ is any solution of $f(x) \equiv 0 \pmod p$. Then $(b - a) g(b) \equiv 0 \pmod p$. Since $\mathbb{Z}/p\mathbb{Z}$ has no zero divisors, either $b \equiv a \pmod p$, or $g(b) \equiv 0 \pmod p$. The first case gives exactly one residue ($a$ itself); the second case gives at most $m-1$ residues by the inductive hypothesis. So the total number of solutions is at most $1 + (m-1) = m$. This completes the induction. $\blacksquare$

We use three ingredients already established: the division property of order, Lagrange's Theorem on polynomial roots mod $p$, and basic properties of Euler's totient (specifically $\sum_{d \mid m} \varphi(d) = m$).

Setup. For each divisor $d$ of $p-1$, let $\psi(d)$ denote the number of $a \in \{1, \dots, p-1\}$ with $\operatorname{ord}_p(a) = d$. Every residue $a \in \{1,\dots,p-1\}$ has some order dividing $p-1$ (Corollary above), so

Step 1: bounding $\psi(d)$ via Lagrange. Fix a divisor $d \mid (p-1)$. Consider the polynomial congruence

By the Lemma (Lagrange's theorem), this has at most $d$ solutions mod $p$. Now if $\operatorname{ord}_p(a) = d$, then $a^d \equiv 1 \pmod p$, so $a$ is one of these at-most-$d$ solutions. Hence the elements of order exactly $d$ form a subset of the (at most $d$) roots of $x^d - 1 \equiv 0$.

Step 2: if there is one element of order $d$, there are exactly $\varphi(d)$. Suppose $\psi(d) > 0$, and fix some $a_0$ with $\operatorname{ord}_p(a_0) = d$. Consider the $d$ powers

These are pairwise incongruent mod $p$: if $a_0^i \equiv a_0^j \pmod p$ with $0 \le i < j \le d-1$, then $a_0^{j-i} \equiv 1 \pmod p$ (using invertibility of $a_0$ mod $p$) with $0 < j - i < d$, contradicting that $d$ is the least positive exponent giving $1$. So these $d$ powers are $d$ distinct residues mod $p$. Each of them satisfies $(a_0^i)^d = (a_0^d)^i \equiv 1^i \equiv 1 \pmod p$, so each is a root of $x^d - 1 \equiv 0 \pmod p$. Since that congruence has at most $d$ roots (Step 1) and we have exhibited $d$ distinct roots, these powers $a_0^0, \dots, a_0^{d-1}$ constitute all the roots of $x^d \equiv 1 \pmod p$. In particular, every element of order exactly $d$ must be among $\{a_0^0, \dots, a_0^{d-1}\}$, since such elements satisfy $x^d \equiv 1$. So it remains to count, among these $d$ powers, how many have order exactly $d$ (as opposed to a proper divisor of $d$).

Claim: $\operatorname{ord}_p(a_0^i) = \dfrac{d}{\gcd(i,d)}$ for $0 \le i \le d - 1$. Proof of claim. Let $g = \gcd(i, d)$, and let $e = \operatorname{ord}_p(a_0^i)$. We show $e = d/g$. First, $(a_0^i)^{d/g} = a_0^{i d / g} = (a_0^d)^{i/g} \equiv 1 \pmod p$ — here $i/g$ is an integer since $g \mid i$. So $e \mid (d/g)$ by the division property of order (applied to the element $a_0^i$, whose order is $e$, with $k = d/g$). Conversely, $(a_0^i)^e \equiv 1 \pmod p$ means $a_0^{ie} \equiv 1 \pmod p$, so by the division property applied to $a_0$ (order $d$), we get $d \mid ie$. Write $i = g i'$, $d = g d'$ with $\gcd(i', d') = 1$ (dividing by the gcd). Then $d \mid ie \iff g d' \mid g i' e \iff d' \mid i' e$. Since $\gcd(d', i') = 1$, Euclid's lemma / Bézout gives $d' \mid e$, i.e. $(d/g) \mid e$. Combining $e \mid (d/g)$ and $(d/g) \mid e$ with both positive gives $e = d/g$, proving the claim. $\square$

Step 3: finishing the count. By the claim, $a_0^i$ has order exactly $d$ if and only if $\gcd(i, d) = 1$. The number of $i \in \{0, 1, \dots, d-1\}$ with $\gcd(i,d) = 1$ is, by definition, $\varphi(d)$ (note $\gcd(0,d) = d \ne 1$ unless $d=1$, consistent with the definition). Since we showed the elements of order $d$ among $1,\dots,p-1$ are exactly $\{a_0^i : \gcd(i,d)=1\}$, we conclude

Step 4: $\psi(d) > 0$ for every $d \mid (p-1)$. We now know each $\psi(d)$ is either $0$ or $\varphi(d)$, so

Summing over all $d \mid p-1$ and using $(\ast)$:

where the last equality is the standard totient identity $\sum_{d\mid m}\varphi(d) = m$ applied to $m = p-1$ (proved by partitioning $\{1,\dots,m\}$ according to $\gcd(k,m)$). Since the sum of the $\psi(d)$ equals the sum of the (larger-or-equal) $\varphi(d)$, and each term satisfies $\psi(d) \le \varphi(d)$, every single inequality must be an equality: if some $\psi(d_0) < \varphi(d_0)$ strictly, the total sum $\sum \psi(d)$ would be strictly less than $\sum \varphi(d) = p-1$, contradicting $(\ast)$. Hence

This proves parts (1) and (2). For part (3), set $d = p - 1$: the number of primitive roots is $\psi(p-1) = \varphi(p-1)$. Since $\varphi(m) \ge 1$ for every positive integer $m$ (as $\gcd(m,m)=m$, but more simply $\varphi(1)=1$ and generally $\varphi(m)\ge 1$ because $1$ is always coprime to $m$), we get $\varphi(p-1) \ge 1$, so at least one primitive root exists. $\blacksquare$