Motivation
Euler's theorem bounds every unit's cycle, but it does not promise one cycle containing all units. A primitive root supplies exactly that: every unit becomes a power of one chosen residue. Multiplication is then addition of exponents, and a nonlinear-looking power equation becomes a linear congruence. The existence proof depends on a feature of prime moduli that composite moduli may lose: polynomial root bounds over a field.
Definitions
Definition 5.1.1
(Primitive roots and discrete logarithms)
A primitive root modulo is a unit with . Its powers are then all the units, without repetition. Relative to , the discrete logarithm of a unit is the unique exponent class modulo satisfying .
A discrete logarithm is a residue class of exponents; choosing an integer representative is a further convention. Its definition does not assert that it is easy to compute. Here small tables illustrate the algebra, rather than suggesting a general efficient algorithm.
Theorem/Proposition
Theorem 5.1.2
(Primitive roots for primes)
For every prime , the unit group modulo has a primitive root. It has exactly primitive roots. The prime is included: its sole unit has order , and .
Theorem 5.1.3
(Solving a power equation in a cyclic unit group)
Suppose is a primitive root modulo , set , and write a unit . For positive , the unit solutions of correspond to through . Thus there are no unit solutions unless ; otherwise there are exactly .
Proof sketch or proof idea
Proof
(Prime-power parts combined by coprime orders)
First, a nonzero polynomial of degree over a field has at most roots. If is a root, polynomial division gives a factor ; induction on degree bounds the remaining roots, since a field has no zero divisors. This applies to residues modulo a prime.
Let be odd and write . For each prime , the polynomial has fewer than roots, so choose a nonzero residue with . Let its order be . Euler gives . Since , the exponent of in is exactly . Therefore
has order by the order-of-a-power formula.
Commuting elements with coprime orders have product of order . Indeed, if , then belongs to both cyclic subgroups. Its order divides both , hence it is . Thus and , forcing ; exponent does work. Repeatedly applying this fact shows has order . This proves existence.
Every unit is . Its order is , so it is primitive exactly when . There are such exponent classes.
Proof
(Exponent coordinates turn the power equation linear)
Write and . Then is equivalent to by the order criterion, and the linear-congruence theorem gives the count. The exceptional exponent modulus has one class and the same conclusion directly.
Proof X-ray
Where the field and the coprime orders are used
The field enters exactly once: the root bound guarantees that , of degree , cannot vanish at all nonzero residues. That gives an element whose order divides but not , so carries the full power . The chosen element need not be a generator; the power strips the unwanted factors and has order exactly .
The key move is the coprime-order lemma, which needs two hypotheses. Commutativity makes split into powers, and coprime orders make the two cyclic subgroups meet only in . In the unit group both hold by construction, and the prime-power orders multiply to . Modulo the root bound fails, since has four roots, and indeed no unit has order .
Worked examples
Worked example 5.1.4
(A complete power table modulo seven)
The powers modulo are . Since all six units occur, is primitive. The primitive powers have exponents coprime to , namely , so the primitive roots are and . In particular, maximal order does not mean the numerically largest residue.
Worked example 5.1.5
(From a cubic to a linear congruence)
Solve . Since in the table, write and solve . The solutions are , giving . Their cubes all have remainder . A nonunit cannot solve the equation because its cube would not be a unit.
Worked example 5.1.6
(Prime and composite moduli behave differently)
Modulo , the units all square to , so no unit has order ; there is no primitive root. Also has four roots modulo , exceeding its degree. This does not contradict the polynomial bound, whose field hypothesis fails. By contrast, has order modulo : its order is divisible by from reduction modulo and divides , so it is or ; excludes .
What a generator adds to Euler's theorem
Euler's theorem tells us that every unit returns to one after a shared exponent. It does not say that powers of a single unit reach the others. A primitive root adds a complete coordinate system: each unit is assigned one exponent class, and multiplication corresponds to addition of coordinates. This is a stronger structural claim than periodicity, and it requires its own proof.
The distinction is visible modulo eight. Every unit has a short cycle, yet none has a cycle long enough to include all four units. The separate two-element cycles cannot be joined merely by choosing a more convenient representative. A representative change leaves the residue class and its order unchanged. Thus a failure of cyclicity is a property of the multiplication structure, not a problem with the chosen notation.
Why the polynomial argument needs a field
A root-count proof repeatedly factors out a linear term and argues that every other root must be a root of the remaining factor. This implication uses the absence of zero divisors. Over a field, if a product vanishes and one factor is nonzero, the other factor must vanish. In a residue ring with composite modulus, two nonzero factors can have zero product. A degree bound that was safe over the field can therefore fail.
For the existence proof, the polynomial is chosen with degree strictly smaller than the number of nonzero field elements. Hence it cannot vanish at all of them. The selected element is not claimed to be a generator immediately. It only contributes one full prime-power part of the desired order. This is the central strategic move: solve several smaller order requirements separately, then combine them using coprimality.
Counterexample mode
Orders of a product need not multiply
A tempting shortcut is to multiply any two units of orders and and expect order . Modulo , the units and both have order , since and . Their product is , of order , not . Here the subgroups generated by and coincide, so the intersection argument fails. With coprime orders the conclusion holds: has order , has order , and has order , so is a primitive root modulo , in agreement with the power table.
Counting generators without listing every cycle
Once one generator is known, the order formula classifies every other generator at once. Exponents coprime to the group size preserve the full cycle, while exponents with a common factor visit a shorter subcycle. This turns the generator count into a count of coprime exponent classes. The answer depends on the group size, rather than on which particular generator was selected.
There is no circularity in that count. Existence of one generator was proved first by the polynomial construction. Only afterwards do we use its powers to enumerate all units and count those having maximal order. Attempting to start by writing every unit as a power of an unspecified generator would assume the main theorem. Keeping the existence and enumeration stages separate is a useful general habit in algebraic proofs.
A small prime makes the distinction clear. Knowing that a candidate has a power equal to one at the full exponent is merely the Euler condition. To show it is a generator, one must exclude every proper divisor of that exponent as a return time. Checking only that the candidate is not one excludes the order one case but leaves all other proper orders open. The earlier divisor-testing method provides a short and complete certificate.
Quick check
(Show that is a primitive root modulo by computing only two powers.)
The proper divisors of that must be excluded are all divisors of or of .
Solution · Answer
The order of divides . If it were a proper divisor, it would divide or . But and , neither of which is . Hence the order is , and is a primitive root.
Solving equations after changing coordinates
The map from exponent classes to units is a bijection. Consequently solving an equation in exponent coordinates neither creates extra unit solutions nor loses valid ones. A linear congruence in the exponent may have several solutions; those yield distinct units because the coordinate map is injective. This is why the linear-congruence solution count transfers directly to the original power equation.
The solvability condition uses the logarithm of the target, but it does not depend on the particular integer chosen to represent that logarithm. Any two representatives differ by the group size, which is divisible by the gcd appearing in the condition. Thus changing the representative preserves whether that gcd divides the target exponent. This is a small well-definedness check that should accompany a statement involving exponent classes.
Nor does changing the primitive root change the number of solutions. Any new primitive root is a coprime power of the old one, so changing coordinates multiplies exponents by a unit modulo the group size. A linear congruence is carried bijectively to the corresponding new one. The numerical logarithms change, but the original equation and its solution set do not.
Concept lensStructural
Power equations become an image-and-fiber problem
In exponent coordinates, raising a unit to a fixed power is multiplication of its exponent by a fixed integer. The gcd with the cycle length measures both the kernel size (the number of units whose given power is one) and the number of preimages of any attainable target. Targets outside the image have no preimages. This is the same structure already visible in a linear congruence with a nonunit coefficient.
Quadratic residues as a first consequence
For an odd prime, choose a primitive root and consider squaring units. The exponent cycle has even length. A square therefore has an even exponent, and every even exponent is obtained by doubling an exponent. Exactly half of the nonzero residues are squares. Each such residue has two square roots among the units, corresponding to the two solutions of the doubled-exponent congruence. They are negatives of each other, since a nonzero root cannot equal its negative in odd characteristic.
This conclusion is a useful introduction to quadratic residues, but it does not prove quadratic reciprocity or supply a general efficient square-root algorithm. The generator table solves small examples, while large instances require additional computational ideas. Distinguish the algebraic classification of possible solutions from the difficulty of finding their coordinates. Discrete logarithms are defined by uniqueness; their computational cost is a separate question.
The boundary of the current argument
The prime-power example shows that some composite moduli do admit primitive roots. The modulus eight example shows that some do not. Together they prevent two false generalizations, but they do not establish a complete classification. A full treatment would need to examine lifting from odd primes to their powers and the interaction with factors of two, then prove the corresponding necessity statements. Those topics remain outside the proof completed on this page.
This boundary is mathematical rather than merely administrative. The polynomial root argument works over a field, so it cannot simply be repeated unchanged over every composite residue ring. Any extension must replace the missing hypothesis with new reasoning. Recognizing where a proof stops working is often the first step toward the correct next theorem.
Common mistakes
Common mistake
(Checking the full exponent instead of every proper divisor)
A unit with and need not be a primitive root: Euler's theorem gives the second condition for every unit. Modulo , the unit satisfies but already , so its order is . Primitivity requires for every prime . Primitive roots need not exist for composite moduli at all, and the proof above covers prime moduli only.
Common mistake
(Reducing exponents modulo instead of modulo )
Exponent coordinates live modulo , while the values live modulo . For with , the correct congruence is , with the three solutions . Reducing modulo instead gives , so only, and the solutions and are lost. The solution count also concerns a unit target and unit solutions; a zero target needs a separate divisibility analysis.
Summary
Field root bounds produce elements with each required prime-power order. Their coprime-order product generates every nonzero residue modulo a prime. Once a generator is fixed, power equations become linear congruences in exponent classes.
Exercises
Quick check
(Using the primitive root modulo , list all primitive roots modulo . Use the order formula instead of recomputing every power cycle.)
Solution · Answer
The exponents coprime to are . Their powers of modulo are respectively. These are exactly the primitive roots, because each has order and every unit is a power of .
Quick check
(Solve , and prove that has no solution. Use the power table for .)
Solution · Answer
Since , the first equation is , with solutions modulo . Thus modulo . For target , the equation is , impossible since . The residue does not solve either unit-target equation, so these conclusions exhaust all residues.