In a finite field, nonzero elements form a group under multiplication. A generator of that group expresses every nonzero element as one of its powers. Finding one in a small example is useful, but examples alone do not prove that a generator always exists. We prove a slightly more general theorem and use it to translate multiplication into arithmetic with exponents.
From element orders to one large order
Let be a finite subgroup of the multiplicative group of a field , and let . By Lagrange's theorem every element has finite order dividing . Let be the least common multiple of all these orders. We first construct an element of order . The construction needs one lemma about products.
Lemma 8.1.1
(Orders of commuting elements multiply when coprime)
Let be commuting elements of a group with finite orders and . Then has order .
Proof
(The intersection of and is trivial)
Commutativity gives . If , then lies in both and . The element has order dividing both and , so it is 1. Thus , and both and divide ; since they are coprime, divides .
For each prime dividing , write for the largest power of dividing . Some element has order divisible by : otherwise no order in the least common multiple would contain that power. Write with , and set . The order-of-a-power formula gives .
The elements commute because multiplication in a field is commutative, and their orders are powers of distinct primes, hence pairwise coprime. Applying the lemma repeatedly shows that has order . If , take .
A polynomial root count completes the proof
Theorem 8.1.2
(Finite subgroups of a field's unit group are cyclic)
Every finite subgroup of the multiplicative group of a field is cyclic. In particular, if is finite with elements, then is cyclic of order .
Proof
(At most roots, at least powers)
Every element of has order dividing , so every element is a root of . A nonzero polynomial of degree over a field has at most roots, giving . On the other hand, has distinct powers in , so . Hence and those powers exhaust . For a finite field with elements, take .
Proof X-ray
Three hypotheses, three uses
Each hypothesis of the theorem enters at exactly one step. Finiteness of makes exist and gives , since Lagrange's theorem bounds every order by a divisor of and the powers of are distinct elements of . Commutativity of the field is what allows the lemma to combine the elements into one element of order . The field property enters last: only a field guarantees that has at most roots, and this turns the trivial inequality into equality. The closing move is that all of lies among the roots of one polynomial of degree , while alone already provides of them.
The theorem proves existence; it does not say that every nonzero element is a generator.
Counterexample mode
The root bound fails in a ring with zero divisors
Claim: every finite group of units in a commutative ring is cyclic. Take the ring , whose unit group is . Here , and modulo 8, so every element has order at most 2 and there is no element of order 4. The group is not cyclic. The polynomial has four roots in this ring, more than its degree, which is exactly the bound the proof needs. In a field, has at most two roots.
Worked example 8.1.3
(Which elements of the prime field with 7 elements are generators)
In , the element has and , so . Its order divides 6, but it is neither 1, 2 nor 3 because , and are all different from 1. Thus its order is 6 and it generates . In contrast, and , so 2 has order 3 and is not a generator. Checking all six elements gives orders for , so and are the generators.
Equations in exponents
Proposition 8.1.4
(Power equations become congruences)
Let have order , let be a positive integer, and write and . Then
This equivalence uses the fact that exactly when . Solving the congruence gives every nonzero solution. Treat separately if it might satisfy the original equation; for it does not. The choice of generator is needed to assign exponents, but the set of solutions does not depend on which generator is chosen.
Worked example 8.1.5
(A power equation with two solutions)
Solve in . The element generates : its powers show order 10. Since , write and solve . This is , so and . Hence or . Check: and .
Worked example 8.1.6
(A power equation with no solution)
Solve in . With we have , so requires . The left side is even and the right side is odd modulo the even number 6, so there is no solution. The squares of modulo 7 are , which confirms that 3 is not a square.
Common mistake
(Expecting a unique solution to a power equation)
The congruence need not have exactly one solution, because need not be invertible modulo . It has solutions exactly when divides , and then it has solutions modulo . Over , has two solutions, while over , has none.
Quick check
(How many generators does have, if is one of them? Is a generator?)
Compute the order of modulo 13 directly.
Solution · Answer
The powers of modulo 13 are , so has order 12. In a cyclic group of order 12 generated by , the element is a generator exactly when , which holds for . So there are four generators. The element 3 is not one: , so its order is 3.
Quick check
(How many satisfy ?)
Write with a generator of the cyclic group of order 15.
Solution · Answer
The equation becomes , that is , which has the five solutions modulo 15. So there are exactly five such .