Motivation
Primitive roots exist modulo every prime, but a composite modulus can join several distinct sources of periodicity. A successful classification needs both a construction and an obstruction. The construction must show that a generator gains the full new prime factor in its order at every higher prime power. The obstruction must explain why several individually cyclic pieces may fail to form one cycle after Chinese remainder reconstruction.
We prove that for every integer , a primitive root exists exactly when is two, four, an odd prime power, or twice an odd prime power. The prime-modulus primitive-root theorem from the preceding notes is the named starting result. We also use the proved order-divisibility criterion, Euler's theorem, integer prime factorization, and the Chinese remainder theorem. No additional primitive-root existence theorem is assumed.
The argument distinguishes a residue class modulo a prime from a chosen integer representative. Those representatives become different classes modulo the prime square, and the difference can determine whether the order grows. That small distinction is the reason a correction by one copy of the prime appears in the construction.
Definitions
Definition 5.2.1
(Units, primitive roots, and valuations)
Write for the multiplicative group of unit classes. It has elements. A primitive root modulo is a unit whose order is , equivalently a generator of . The trivial group is cyclic, so the sole unit one is a primitive root modulo two.
For a prime and nonzero integer , let be the largest integer for which . Assertions using a finite value of this valuation exclude .
There are units modulo : exactly the multiples of are excluded. A return exponent of a unit is divisible by its order, and its order divides the number of units. These facts constrain the possible orders but do not alone establish that the largest possible order occurs.
For coprime , the Chinese remainder map induces a group isomorphism . Indeed the ring map preserves multiplication and is bijective; a pair of unit coordinates has a coordinatewise inverse, whose inverse image is a unit. Conversely a unit maps to units. This verifies the unit-group assertion, rather than using a mere equality of cardinalities.
Theorems
Theorem 5.2.2
(Choosing a lift that generates every odd prime power)
Let be odd and let the positive integer be primitive modulo . At least one of and is primitive modulo . Any integer primitive modulo is primitive modulo for every .
Theorem 5.2.3
(Complete classification for moduli at least two)
For , the group is cyclic if and only if
where is an odd prime and . Thus these, and only these, are the moduli with primitive roots.
Proof sketch or proof idea
First secure the order modulo the prime square
Proof
(One correction secures the prime square)
Reduction modulo shows that the order of modulo is a multiple of . It also divides , so it is either or . Therefore is primitive modulo exactly when .
If that condition holds, choose . If it fails, expand the other lift:
All later terms contain . The coefficient is nonzero modulo , since is a unit and is not divisible by . Thus, when the first power is one modulo , the second is not. The new lift still reduces to modulo , so the same order argument makes primitive modulo . This proves the first existence step without searching through all units modulo the square.
One binomial step controls the exact valuation
Proof
(Exact valuation growth gives the full order)
For odd , suppose is finite. Write with . We claim
The binomial expansion begins with . For , its th term has valuation at least , because is divisible by . The last term has valuation , using and . Consequently
The leading coefficient is still a unit modulo , so the valuation is exactly , not merely at least that much. This exactness is what prevents the order from growing too slowly.
Reduction is onto, since every nonzero prime-level class lifts to a unit. A generator therefore reduces to a generator. If is primitive modulo , then but not modulo , hence its difference from one has valuation one. Repeatedly apply the binomial step to obtain
Let be the order of modulo . Reduction modulo gives , while Euler gives . Thus for some . The valuation identity says that this power returns to one modulo exactly when . Hence , proving the full order . The same integer works for every .
Proof X-ray
A return power is not an exact-order certificate
Three facts pin down the order of modulo , and each excludes a different loss. Because reduces to a generator modulo , its order is a multiple of . Euler's theorem gives , so with . The key move is the exact valuation : an inequality would show only that some power returns to , whereas equality shows that for every .
Oddness of is used at one point, the last binomial term: has valuation at least only when . For and the step fails, since rather than . The base case is exactly the square-level primitivity secured by the first step.
Constructing the allowed even moduli
Proof
(Existence for the even moduli)
The unit groups modulo and are explicitly cyclic: their generators are and , respectively. For odd , the preceding theorem constructs a primitive root modulo every from a prime generator.
Since is trivial, CRT gives . A generator modulo therefore has a unique odd lift modulo , of the same order. Given a representative , choose if it is odd and if it is even. The oddness check matters: an even representative is not a unit modulo the doubled modulus. This completes existence for every listed form.
Too many square roots of one obstruct a single cycle
Proof
(Four square roots of one and necessity)
In a finite cyclic group of order , writing elements as powers of a generator makes equivalent to . There are solutions. Thus a unit group containing four distinct square roots of one cannot be cyclic.
For , the four classes
are distinct units modulo and all square to . Expanding leaves , whose last two terms vanish modulo . Distinctness uses ; modulo the proposed classes coincide in pairs. Hence the powers with do not admit primitive roots.
Every odd prime-power unit group has the two distinct roots one and minus one. If a modulus has two distinct odd prime factors, choose each sign independently in those two CRT coordinates and choose one in every other coordinate. The four reconstructed units are distinct and square to one. The same construction works when the modulus has both a factor four and an odd prime factor: the modulo-four coordinate also has the distinct signs. A higher power-of-two coordinate already has four roots and can be combined with ones elsewhere. None of these unit groups is cyclic.
To see that no modulus has been missed, write with distinct odd primes and . If , then forces , and only survive. If , only survive. If , the independent odd signs rule out cyclicity. The surviving forms are precisely those in the theorem. This is the necessity direction, not just a collection of failed examples.
Proof X-ray
One invariant rules out every excluded modulus
The necessity proof uses a single invariant: the number of solutions of . In a cyclic group it is at most two, since has solutions; this is the only place cyclicity enters. Everything else produces four solutions. For with they are explicit, and the hypothesis is exactly what keeps different from . Otherwise CRT is the engine: two coordinates that each contain distinct signs give independent choices. The final factorization count shows that these two mechanisms cover every modulus outside the list.
Worked examples
Worked example 5.2.4
(A prime generator can have the wrong lift)
The integer is primitive modulo because its class is . But , so its order modulo is only rather than . Changing to gives , of valuation . Therefore is primitive modulo for every . Modulo its order is ; its sixth power is , so the smaller candidate exponent does not suffice. The correction changed a representative at the prime level into a genuinely different class at the square level.
Worked example 5.2.5
(An odd lift produces a generator modulo fifty)
The integer is primitive modulo since , and has . Hence generates the units modulo . It is even, so it is not a unit modulo . The required odd lift is , whose order remains . Direct checks give and . These exclude the maximal proper divisors and of the group order , providing an independent exact-order certificate. There are primitive roots modulo , obtained by taking coprime powers of this generator.
Worked example 5.2.6
(Cyclic coordinates need not give a cyclic product)
For , the local unit groups are cyclic of orders and . Nevertheless the four classes all square to modulo , so the global group is not cyclic. The generator candidates in the two coordinates return simultaneously according to their least common multiple, not their product. In particular, has order modulo , while . A long power cycle is not automatically a complete cycle.
Concept lensStructural
CRT synchronizes return times
An element of a product with component orders has order , because it returns exactly when both component orders divide the exponent. For cyclic factors of orders , every component order divides its factor order, so every product-element order divides ; a pair of generators attains it. Thus the product is cyclic exactly when . Two odd prime-power unit groups have even orders, so their cycles share a factor two and cannot combine into a cycle as long as the product size. CRT preserves multiplication; it does not assert that independent cycles have coprime lengths.
Common mistakes
Counterexample mode
Not every lift of a primitive root is primitive modulo the square
A plausible claim is that any integer which is primitive modulo an odd prime stays primitive modulo . Modulo the integer is primitive, and so is . But , so , and . Hence , and has order , not . By contrast , so itself is primitive modulo . The correct statement is the lifting theorem: at least one of and works, and once the order modulo is maximal, every higher power follows with no new choice of generator.
Common mistake
(Assuming cyclic local factors give a cyclic product)
A cyclic unit group in each CRT coordinate is not enough when two coordinates have orders with a common factor. Modulo , the factors and are cyclic of orders and , but every unit satisfies , so no unit has order .
Common mistake
(Transferring the field root bound to a composite modulus)
The bound “a quadratic has at most two roots” holds over a field. Modulo the four roots of are real; what they contradict is cyclicity, not the polynomial bound. When testing orders or counting generators, also keep the value modulus apart from the exponent modulus .
Summary
A one-prime correction secures a primitive root modulo the odd prime square, and exact valuation growth proves maximal order at every higher power. CRT transfers the generator to twice that power. Four independent square roots of one rule out all remaining modulus types, completing both directions of the classification for .
Exercises
Quick check
(Fix a positive primitive root modulo an odd prime . Prove that among the lifts modulo , exactly one fails to be primitive. Explain why checking just and always finds a successful lift.)
Solution · Answer
Write , using Fermat. Binomial expansion gives . The coefficient of is a unit modulo , so exactly one makes the bracket zero. Precisely that lift has order ; all others have order . If fails, succeeds; if it succeeds, no correction is needed. The theorem guarantees at least one of the pair, not that both are always primitive.
Quick check
(Construct a primitive root modulo starting from modulo , and give a direct order certificate modulo .)
Solution · Answer
Since has valuation , the integer is primitive modulo . Its odd lift modulo is . One computes and . The order divides , but does not divide or , so it is . These are the maximal proper divisors and , so every smaller divisor is excluded.
Quick check
(Which of admit primitive roots? For each permitted modulus, give one generator justified by the construction or earlier examples.)
Solution · Answer
Exactly qualify. Generators are respectively : generates modulo and is already odd, so it serves modulo ; generates modulo because has , and it is already odd, so it serves modulo ; works for the powers of and of by the valuation test; was proved for . The other moduli have a forbidden power-of-two factor or at least two distinct odd prime factors, as specified in the classification.
Quick check
(Explain why the valuation step cannot be copied unchanged for . Use as a concrete calculation, and relate it to the failure of lifting a primitive root from to .)
Solution · Answer
Here , but , rather than . In the binomial proof the last term need not have valuation at least for , so it can interact with the first term. The integer generates modulo but has order modulo , not the required . This is a genuine group-structure obstruction, as the four roots of one also show, rather than only a gap in the odd-prime proof.