The index table
Click two units to multiply them: their indices add mod p − 1.
The power map x ↦ xℓ
d = gcd(ℓ, p − 1)
Solutions of xℓ ≡ 1
Size of the image H
Lesson 02 · The multiplicative group · 50–65 minutes
Index and the Power Map
Lesson 01 showed that a primitive root g writes every unit as a power, n ≡ gk. The exponent k is the index of n, a logarithm for arithmetic mod p: it turns multiplication into addition mod p − 1. With it, questions about powers mod p become linear congruences. You will use it to count the solutions of xℓ ≡ 1, find which units are ℓ-th powers, split the units into cosets, and prove Wilson's theorem.
Where this lesson is headed
ind(ab) ≡ ind a + ind b (mod p − 1), #{x : xℓ ≡ 1} = gcd(ℓ, p − 1)
In words: in index coordinates the unit group is just the integers mod p − 1 under addition. Raising to the ℓ-th power becomes multiplying by ℓ, so everything about x ↦ xℓ is decided by d = gcd(ℓ, p − 1): it is d-to-one, its image H is the set of units whose index is divisible by d, and the units split into d cosets of H.
You will use
Primitive roots exist, and 1, g, …, gp−2 are the p − 1 units, each once (Lesson 01). Lagrange's bound: a degree-d polynomial has at most d roots mod p (Lesson 01, step 5). The linear congruence rule: c·X ≡ b (mod m) is solvable exactly when gcd(c, m) divides b, and then it has gcd(c, m) solutions mod m (Growing Clock 02, step 4).
p: an odd prime; g: a primitive root mod p
indg(n): the k in {0, …, p − 2} with gk ≡ n
ℓ: an exponent; d = gcd(ℓ, p − 1)
H: the image of x ↦ xℓ (the ℓ-th powers)
coset: a set gjH of units
01. A logarithm for arithmetic mod p
Start with p = 7 and its primitive root g = 3. The powers 30, …, 35 are 1, 3, 2, 6, 4, 5, so ind 2 = 2, ind 6 = 3, and so on. Then choose an exponent ℓ and watch where x ↦ xℓ sends each unit.
Guided experiments
Do these in order. "Set this up" chooses p, g and ℓ.
Why a logarithm?
Ordinary logarithms turn products into sums: log(ab) = log a + log b. The index does the same thing mod p, except that the sums are taken mod p − 1, because gp−1 ≡ 1 wraps the exponents around.
So a question like "solve x3 ≡ 5 (mod 13)" becomes "solve 3X ≡ ind 5 (mod 12)", a linear congruence you already know how to handle.
The index is also called the discrete logarithm. Computing it for large p is believed to be hard, which is why it is used in cryptography; for the primes here a table is instant.
02. In index coordinates, everything is linear
Each step has the general statement on the left and your p, g and ℓ from Stage 01 on the right.
1
The index is well defined, and it is a logarithm
Since 1, g, …, gp−2 are the p − 1 units each exactly once, every unit n equals gk for exactly one k in {0, …, p − 2}. Because gp−1 ≡ 1, gk ≡ gk′ exactly when k ≡ k′ (mod p − 1). So
ind(ab) ≡ ind a + ind b, ind(am) ≡ m·ind a (mod p − 1)
since gind a + ind b = gind agind b ≡ ab.
2
The index of −1
h = g(p−1)/2 satisfies h2 ≡ 1, so it is a root of x2 − 1. By Lagrange that polynomial has only the roots ±1, and h ≢ 1 because (p − 1)/2 < p − 1 = ord g. So
g(p−1)/2 ≡ −1, ind(−1) = (p − 1)/2
3
Orders from indices
(gk)m ≡ 1 ⇔ (p − 1) | km ⇔ (p − 1)/gcd(k, p − 1) divides m. So
ord(gk) = (p − 1)/gcd(k, p − 1)
In particular gk is a primitive root exactly when gcd(k, p − 1) = 1, which recovers the count φ(p − 1) from Lesson 01.
4
Solving xℓ ≡ a
Write x = gX. Then xℓ ≡ a becomes the linear congruence
ℓ·X ≡ ind a (mod p − 1)
With d = gcd(ℓ, p − 1), it is solvable exactly when d | ind a, and then it has exactly d solutions X mod p − 1, so d solutions x. For a = 1 (ind 1 = 0) there are always d solutions.
5
The ℓ-th powers form a subgroup of size (p − 1)/d
By step 4, a is an ℓ-th power exactly when d | ind a. So
H = {ℓ-th powers} = {g0, gd, g2d, …} = {d-th powers}
has (p − 1)/d elements, each hit by exactly d values of x. H is closed under products and inverses (indices divisible by d add and negate to indices divisible by d): a subgroup. If d = 1 the power map is a bijection.
6
The cosets of H
Sort the units by ind n mod d. The class j is gjH = {gjh : h ∈ H}, and the d classes C0, …, Cd−1 have equal size (p − 1)/d. Multiplying adds classes:
a ∈ Ci, b ∈ Cj ⇒ ab ∈ Ci+j mod d
This labeling depends on the choice of g only through a relabeling of the classes; the partition itself does not (step 5 describes H without g). Lesson 07 uses exactly this with d = 4.
7
An application: Wilson's theorem
(p − 1)! is the product of all units, g0g1⋯gp−2, whose index is
0 + 1 + ⋯ + (p − 2) = (p − 1)(p − 2)/2
Since p − 2 is odd, this is (p − 1)/2 times an odd number, which is ≡ (p − 1)/2 (mod p − 1). By step 2 that is ind(−1). So
(p − 1)! ≡ −1 (mod p)
03. The power map theorem
Assemble the argument, then test it on every prime below 1000.
Theorem. Let p be prime, g a primitive root, ℓ ≥ 1 and d = gcd(ℓ, p − 1). Then x ↦ xℓ on (ℤ/pℤ)× is d-to-one onto the subgroup H = {n : d | indg n} of order (p − 1)/d; xℓ ≡ a is solvable exactly when a ∈ H, with d solutions; and the units are the disjoint union of the d cosets gjH.
Complete proof
Index. k ↦ gk is a bijection from ℤ/(p − 1)ℤ to (ℤ/pℤ)× turning addition into multiplication (Lesson 01). Its inverse is indg, so ind(ab) ≡ ind a + ind b.
Power map. In these coordinates x ↦ xℓ is X ↦ ℓX on ℤ/(p − 1)ℤ. The congruence ℓX ≡ b has solutions exactly when d | b, and then d of them. Hence the image is H = {n : d | ind n}, of size (p − 1)/d, and every element of H has exactly d preimages. H is a subgroup because dℤ/(p − 1)ℤ is closed under addition and negation, and its cosets are the classes of ind n mod d, each of size (p − 1)/d.
Wilson. ind(−1) = (p − 1)/2 because g(p−1)/2 is a square root of 1 other than 1. The product of all units has index (p − 1)(p − 2)/2 ≡ (p − 1)/2, so (p − 1)! ≡ −1. ∎
Computer check
For every odd prime below 1000 and every ℓ from 1 to p − 1: counts the solutions of xℓ ≡ 1, the size of the image and the number of preimages of each image point, and compares them with gcd(ℓ, p − 1). Also checks ind(ab) ≡ ind a + ind b for a random sample and Wilson's theorem for every prime.
Not run yet.
Exit problem
Use p = 13 and g = 2.