Primitive roots and cyclic unit groups

For modulus m at least two, a primitive root g is a unit of order φ(m). Its first φ(m) powers are all distinct: equality between two earlier powers would give a smaller return to one. Since there are exactly φ(m) units, those powers enumerate every unit. Conversely, a unit whose powers enumerate all units must have that order. This is the meaning of saying the unit group is cyclic.

If g is a primitive root, the order of g to the power k is φ(m) divided by gcd(k, φ(m)). Indeed, its t-th power returns when φ(m) divides kt, and reducing by the gcd gives the smallest possible positive t. Thus the powers that remain generators are exactly the exponents coprime to φ(m), giving φ(φ(m)) primitive roots whenever the group is cyclic.

Let N = φ(m) and assume a candidate g is a unit. Its order divides N. To prove the order equals N, it is enough to test that g to the power N/q is not one for every distinct prime q dividing N. If the order d were a proper divisor, N/d would contain a prime q, and d would divide N/q, contradicting that test. Testing all integers below N is unnecessary.

For prime modulus p, the nonzero residues do have a primitive root. One proof uses the fact that a nonzero polynomial of degree d over a field has at most d roots, together with the possible element orders. The field assumption matters: the same root bound need not hold over a composite modulus. We use the existence theorem here while checking concrete candidates directly, so the certificate for a particular generator remains fully inspectable.

For m at least two, primitive roots exist exactly for m = 2, m = 4, odd prime powers p to the power k, and twice those odd prime powers, with k positive. The modulus one is outside our convention; if one includes its trivial unit group, cyclicity can be treated separately. In particular, the unit group modulo eight is not cyclic, even though its four elements form a perfectly valid group.

The obstruction is visible in a tiny table: each unit modulo eight squares to one, so no unit has order four. More generally CRT decomposes unit information over coprime factors, and the combined orders are least common multiples rather than automatically products. A primitive root also gives discrete logarithms as coordinates, but existence of those coordinates is not an efficient algorithm for finding them. Separate a structural theorem from a computational procedure and from an application’s security assumptions.