Primitive root modulo n — generators of the multiplicative residue group

A primitive root modulo n is an integer that generates the multiplicative group of units modulo n. Article explains definition, existence, tests, examples and applications.

Overview

A primitive root modulo n is an integer g whose powers produce every invertible residue modulo n. More precisely, g is a primitive root modulo n when the set {g^k mod n : k = 1,2,...} equals the group of units (Z/nZ)^×, the numbers between 1 and n−1 that are coprime to n. In group-theoretic language, g is a generator of the multiplicative group modulo n and its multiplicative order is φ(n), Euler's totient of n. For a compact introduction to modular arithmetic concepts see modular arithmetic and related background here. $g^{x}\equiv m{\pmod n}$

Definition and basic example

If every integer m with 1 ≤ m < n that is coprime to n can be written as g^x ≡ m (mod n) for some integer x, then g is a primitive root modulo n. For example, 3 is a primitive root modulo 7 because the powers of 3 cycle through all residues 1,2,3,4,5,6 in some order: 3^1 ≡ 3 (mod 7) $3^{1}\equiv 3\ {\pmod 7}$ , 3^2 ≡ 2 (mod 7) $3^{2}\equiv 2\ {\pmod 7}$ , 3^3 ≡ 6 (mod 7) $3^{3}\equiv 6\ {\pmod 7}$ , 3^4 ≡ 4 (mod 7) $3^{4}\equiv 4\ {\pmod 7}$ , 3^5 ≡ 5 (mod 7) $3^{5}\equiv 5\ {\pmod 7}$ , 3^6 ≡ 1 (mod 7) $3^{6}\equiv 1\ {\pmod 7}$ . By contrast, 2 is not a primitive root modulo 7 because 2^3 ≡ 1 (mod 7), so its order is 3 rather than 6. $1,2,\ldots ,6$

Characteristics and tests

Order: The multiplicative order of g modulo n is the smallest positive integer t with g^t ≡ 1 (mod n). g is primitive precisely when this order equals φ(n).
Counting primitive roots: When primitive roots exist modulo n, there are exactly φ(φ(n)) distinct primitive roots modulo n.
Practical test: Factor φ(n) into primes q_1,...,q_r. A candidate g is primitive if for every q_i we have g^{φ(n)/q_i} ≠ 1 (mod n). This reduces checking order to a handful of exponentiations.
Powers that remain generators: If g is primitive, then g^k is primitive iff gcd(k,φ(n)) = 1.

Existence and classification

Primitive roots do not exist for every modulus. A classical theorem—proved by Gauss in the 19th century—characterizes exactly which positive integers n admit primitive roots: they are n = 1, 2, 4, p^k, or 2p^k, where p is an odd prime and k ≥ 1. In other words, the multiplicative group (Z/nZ)^× is cyclic only for these n. For example, every odd prime p has primitive roots modulo p; but modulus 8 (which is 2^3) does not admit a primitive root. $2^{3}=8\equiv 1{\pmod 7}$

Examples, algorithms and applications

Finding an explicit primitive root often proceeds by picking small candidates and applying the factor-test described above. For instance, modulo 7 one quickly finds 3 and 5 are generators. Primitive roots underpin several algorithms and cryptographic protocols: the Diffie–Hellman key exchange and many discrete-log based schemes rely on choosing a prime p and a generator g of the group (Z/pZ)^× so that discrete logarithms are hard to compute. They are also useful in pure number theory for constructing character tables, solving congruences, and studying cyclicity properties of residue classes.

Notable facts and distinctions

When a modulus n has primitive roots, the structure of its unit group is as simple as possible: cyclic. Otherwise the unit group decomposes into a product of cyclic groups and has no single generator.
Primitive roots are defined only up to equivalence: multiplying a primitive root by an integer coprime to n or raising it to a power coprime to φ(n) yields another primitive root.
Computationally, the main steps are factoring φ(n) and testing candidates; for large cryptographic primes one uses safe-prime forms to simplify selection of generators.

For further reading on proofs and deeper properties, standard number theory texts and survey articles give complete proofs of existence, counting, and specific construction methods for primitive roots.