Primitive Root

A primitive root modulo a prime p is an integer g whose multiplicative order modulo p is exactly p − 1, meaning that the powers g, g², g³, ..., g^{p−1} run through all nonzero residue classes modulo p. An integer n is a primitive root modulo p if and only if the discrete logarithm problem with base n has maximal complexity: every nonzero residue is reached exactly once before repetition.

Primitive roots exist modulo p for every prime p, but not for every modulus. The complete classification — primitive roots exist modulo m if and only if m is 1, 2, 4, p^k, or 2p^k for an odd prime p — was proved by Gauss and is one of the foundational theorems of elementary number theory. The existence of primitive roots is equivalent to the cyclicity of the multiplicative group (Z/mZ)^×, a structural fact that underlies the theory of Dirichlet characters and the construction of finite fields.

The primitive root is not merely a generator of a cyclic group; it is the coordinate system that makes modular arithmetic look like arithmetic on a circle. The discrete logarithm to a primitive root is the modular analogue of the angle coordinate — and just as Fourier analysis decomposes functions on the circle into harmonics, Dirichlet characters decompose arithmetic on the residues into their spectral components.