The powers of a on (ℤ/pℤ)×
Exponent k0
ak mod p1
ordp(a)?
Lesson 01 · The multiplicative group · 50–65 minutes
Order, Euler's φ, and Primitive Roots
Multiply a nonzero residue by itself again and again modulo a prime p, and the powers must eventually return to 1. How long that takes is the order of the residue. You will find that every order divides p − 1, count exactly how many residues have each order, and prove that some residue always has the largest possible order p − 1. Such a residue, a primitive root, generates every nonzero residue as a power.
Where this lesson is headed
ap−1 ≡ 1 (mod p), ordp(a) | p − 1, #{a : ordp(a) = d} = φ(d) for every d | p − 1
In words: the powers of any a run around a cycle whose length divides p − 1, and exactly φ(d) residues have cycle length d. Taking d = p − 1 shows primitive roots exist, and there are φ(p − 1) of them.
p: an odd prime
a: a residue with p ∤ a
(ℤ/pℤ)× = {1, 2, …, p − 1} under multiplication mod p
ordp(a): the least k ≥ 1 with ak ≡ 1 (mod p)
φ(n): #{1 ≤ k ≤ n : gcd(k, n) = 1}
primitive root: a residue g with ordp(g) = p − 1
01. The powers of a residue
Start with p = 7 and a = 2. The powers 1, 2, 4, 8 ≡ 1 return to 1 after 3 steps, so ord7(2) = 3, and they only visit half the circle. Step through the powers, then try other a and other primes. (Shortcut: Space takes the next power, ← goes back.)
Guided experiments
Do these in order. "Set this up" chooses p and a.
Euler's φ
φ(n) counts 1 ≤ k ≤ n with gcd(k, n) = 1. The counts in the table above keep matching φ of the order, so we need to be able to compute φ.
A composite warning
Primitive roots are special to primes (and a few other moduli). Modulo 8 the units are 1, 3, 5, 7, and each squares to 1: no unit has order φ(8) = 4.
02. From Fermat's theorem to the count of orders
Each step has the general statement on the left and your p and a from Stage 01 on the right.
1
Powers cycle, and the cycle length controls everything
The powers a0, a1, a2, … take at most p − 1 values, so two coincide: ai ≡ aj with i < j. Cancelling ai (a is a unit) gives aj−i ≡ 1. So ordp(a) = n exists, and a0, …, an−1 are distinct.
ak ≡ 1 ⇔ n | k
(Write k = qn + r with 0 ≤ r < n; then ak ≡ ar, which is 1 only for r = 0.)
2
Fermat's little theorem
Multiplication by a permutes 1, 2, …, p − 1. So the products agree:
(a·1)(a·2)⋯(a·(p − 1)) ≡ 1·2⋯(p − 1)
ap−1·(p − 1)! ≡ (p − 1)!
(p − 1)! is a product of units, so it cancels:
ap−1 ≡ 1 (mod p)
By step 1, ordp(a) divides p − 1.
3
Computing φ
Prime powers. Among 1, …, qe, the ones sharing a factor with qe are the qe−1 multiples of q, so φ(qe) = qe − qe−1.
Multiplicativity. If gcd(m, n) = 1, CRT matches k mod mn with the pair (k mod m, k mod n), and k is coprime to mn exactly when both parts are coprime to their moduli. So φ(mn) = φ(m)φ(n).
φ(n) = n ∏q | n (1 − 1/q)
4
Gauss's identity: ∑d | n φ(d) = n
Write the fractions 1/n, 2/n, …, n/n in lowest terms. Each becomes j/d with d | n and gcd(j, d) = 1, and every such j/d occurs exactly once. There are φ(d) fractions with denominator d, and n fractions in all.
5
At most φ(d) residues of order d
Lagrange. A nonzero polynomial of degree d has at most d roots mod p. (If f(r) ≡ 0, divide: f(x) = (x − r)h(x) + f(r) = (x − r)h(x). Another root s ≢ r gives (s − r)h(s) ≡ 0, so h(s) ≡ 0 because p is prime; induct on d.)
Suppose some a has order d. Then 1, a, …, ad−1 are d distinct roots of xd − 1, so they are all its roots. Every element of order d is among them, and aj has order d exactly when gcd(j, d) = 1 (its order is d/gcd(j, d)). So the number N(d) of elements of order d is either 0 or φ(d).
6
Exactly φ(d), so primitive roots exist
Every unit has some order d | p − 1 (step 2), so
∑d | p−1 N(d) = p − 1 = ∑d | p−1 φ(d)
using step 4. Each N(d) ≤ φ(d) by step 5, so equality of the sums forces N(d) = φ(d) for every d. In particular N(p − 1) = φ(p − 1) ≥ 1: a primitive root g exists, and then (ℤ/pℤ)× = {1, g, g2, …, gp−2}.
03. The primitive root theorem
Assemble the argument, then test it on every prime below 1000.
Theorem. Let p be prime. Every a with p ∤ a satisfies ap−1 ≡ 1 (mod p), so ordp(a) | p − 1. For each d | p − 1 there are exactly φ(d) residues of order d; in particular there are φ(p − 1) primitive roots.
Complete proof
Orders. For a unit a, pigeonhole and cancellation give a least n = ordp(a) with an ≡ 1, and division with remainder shows ak ≡ 1 ⇔ n | k.
Fermat. x ↦ ax permutes (ℤ/pℤ)×, so ap−1(p − 1)! ≡ (p − 1)!; cancelling the unit (p − 1)! gives ap−1 ≡ 1, hence n | p − 1.
Counting. By Lagrange's theorem (which uses that ℤ/pℤ has no zero divisors), xd − 1 has at most d roots. If some a has order d, its d powers are all the roots, and exactly φ(d) of them have order d; so N(d) ∈ {0, φ(d)}. Summing over d | p − 1 and using ∑ φ(d) = p − 1 gives N(d) = φ(d) for all d. Taking d = p − 1 yields φ(p − 1) ≥ 1 primitive roots. ∎
Computer check
For every odd prime below 1000, computes the order of every unit directly and compares the count of each order with φ(d); also checks Fermat's theorem for every unit. Strong evidence, but the proof covers every prime.
Not run yet.