An integer g such that the residues g^k (reduced modulo N) produce every residue class coprime to N; equivalently, g generates the multiplicative group (Z/NZ)^×.

Principle

If (Z/NZ)^× is cyclic then a single element g has multiplicative order φ(N) and its powers enumerate all units modulo N.

Demonstration

For N = 7, the integer 3 is a primitive root because powers 3^1,...,3^6 modulo 7 yield 3,2,6,4,5,1, covering all six units; 3 therefore has order φ(7)=6.

Misapplication

Treating an element g as a primitive root when g is not coprime to N or when (Z/NZ)^× is noncyclic (e.g., N = 8) leads to incorrect conclusions about generation of all units.

Consequence

When a primitive root exists, discrete logarithms relative to that root provide a bijection between (Z/NZ)^× and Z/φ(N)Z, enabling cyclic-structure-based arguments and index arithmetic.

Reversal

The opposite situation is an element whose powers generate only a proper subgroup of (Z/NZ)^× (for example an element of order dividing a proper divisor of φ(N)), which does not enumerate all coprime residues.

Boundary

Primitive roots exist for N = 1, 2, 4, p^k, and 2p^k where p is an odd prime; they do not exist for general composite N. The concept applies only to integers coprime to N and to the multiplicative group of units modulo N.

Semantic Tension

Distinguish primitive root from a generator of an additive group or from any element of maximal order in some subgroup; 'primitive' specifically means a generator of the full multiplicative unit group when that group is cyclic.

Synthesis

A primitive root modulo N is an integer generator that, when it exists, endows the multiplicative units modulo N with a cyclic structure so that exponentiation by that integer cycles through every invertible residue.