Primitive root modulo n
In number theory, a primitive root modulo n is an integer g coprime to the positive integer n such that the multiplicative order of g modulo n—the smallest positive integer k for which gk ≡ 1 (mod n)—equals Euler's totient function φ(n), which counts the number of integers up to n that are coprime to n.[1][2] Equivalently, the powers of g modulo n generate every element of the multiplicative group of integers modulo n, denoted (Z/nZ)×, making g a generator of this group when it is cyclic.[3][4] Primitive roots modulo n do not exist for every n; they exist if and only if n = 2, n = 4, n = pr, or n = 2pr, where p is an odd prime and r is a positive integer.[2] For prime p, the number of primitive roots modulo p is exactly φ(p - 1).[5] When they exist, primitive roots characterize the cyclicity of (Z/nZ)×, a property that holds precisely under the above conditions on n.[6] Primitive roots play a central role in analytic and algebraic number theory, enabling the definition of discrete logarithms modulo n—the problem of finding k such that a ≡ gk (mod n) for a in (Z/nZ)×—which underpins algorithms for solving congruences and studying the structure of finite abelian groups.[4] They also facilitate computations like indices (discrete logs base g) and appear in applications such as analyzing repeating decimal expansions and modeling random processes like card shuffling via riffle shuffles.[7][8]Fundamentals
Definition
In number theory, Euler's totient function \phi(n) counts the number of positive integers up to n that are relatively prime to n, and is given by the formula \phi(n) = n \prod_{p \mid n} \left(1 - \frac{1}{p}\right), where the product is over the distinct prime factors p of n.[9][10] An integer g is a primitive root modulo n if \gcd(g, n) = 1 and the multiplicative order of g modulo n is exactly \phi(n).[9][11] The multiplicative order of g modulo n is defined as the smallest positive integer k such that g^k \equiv 1 \pmod{n}.[9][12] In the context of group theory, a primitive root g modulo n generates the multiplicative group of integers modulo n, denoted (\mathbb{Z}/n\mathbb{Z})^*, which consists of the residue classes coprime to n under multiplication modulo n.[6] This group has order \phi(n), and the powers g^0, g^1, \dots, g^{\phi(n)-1} modulo n are all distinct and comprise every element of (\mathbb{Z}/n\mathbb{Z})^*, thereby making the group cyclic.[9][6]Elementary Example
A simple illustration of a primitive root occurs modulo 5, a prime number for which Euler's totient function φ(5) equals 4, meaning the multiplicative group of integers modulo 5 consists of the four units {1, 2, 3, 4} that are coprime to 5.[10][13] Consider g = 2. The successive powers of 2 modulo 5 are computed as follows:| k | 2^k mod 5 |
|---|---|
| 0 | 1 |
| 1 | 2 |
| 2 | 4 |
| 3 | 3 |
| k | 4^k mod 5 |
|---|---|
| 0 | 1 |
| 1 | 4 |
| 2 | 1 |
Existence Conditions
For Prime Moduli
When n = p is a prime number, primitive roots always exist modulo p. This follows from the fact that the multiplicative group (\mathbb{Z}/p\mathbb{Z})^\times is cyclic of order p-1, as established by Fermat's Little Theorem, which states that every non-zero element modulo p satisfies a^{p-1} \equiv 1 \pmod{p}, implying the group order is \phi(p) = p-1.[5] A primitive root modulo p is then a generator of this cyclic group. The cyclicity of (\mathbb{Z}/p\mathbb{Z})^\times for prime p was rigorously proved by Carl Friedrich Gauss in 1801, utilizing properties of quadratic residues to demonstrate the existence of generators.[14] Gauss's proof in Disquisitiones Arithmeticae shows that the group structure ensures elements of order exactly p-1, confirming the presence of primitive roots. A standard proof of existence uses the factorization x^{p-1} - 1 = \prod_{d \mid p-1} \Phi_d(x) over \mathbb{F}_p, where \Phi_d(x) is the d-th cyclotomic polynomial of degree \phi(d). Since x^{p-1} - 1 has exactly p-1 distinct roots (all nonzero elements by Fermat's Little Theorem) and the total degree is \sum_{d \mid p-1} \phi(d) = p-1, each \Phi_d(x) must have exactly \phi(d) roots in \mathbb{F}_p. In particular, \Phi_{p-1}(x) has \phi(p-1) roots, which are elements of order exactly p-1, i.e., primitive roots. Thus, the number of primitive roots modulo p is exactly \phi(p-1) > 0.[15][5]For Composite Moduli
Primitive roots exist modulo a composite integer n if and only if n = 2, n = 4, n = p^k, or n = 2p^k, where p is an odd prime and k \geq 1.[16] For other composite forms, such as higher powers of 2 or products involving multiple distinct odd primes, the multiplicative group (\mathbb{Z}/n\mathbb{Z})^* is not cyclic, so no element achieves order \phi(n).[16] Non-existence arises in cases like powers of 2 greater than 4; for n = 8, \phi(8) = 4, but every odd residue modulo 8 satisfies a^2 \equiv 1 \pmod{8}, so the maximum order is 2.[17] Similarly, for products of distinct odd primes like n = [15](/page/15) = 3 \times 5, \phi(15) = 8, but the maximum order is \operatorname{lcm}(\phi(3), \phi(5)) = \operatorname{lcm}(2, 4) = 4 < 8.[16] The Chinese Remainder Theorem plays a key role, as (\mathbb{Z}/n\mathbb{Z})^* \cong \prod (\mathbb{Z}/p_i^{k_i}\mathbb{Z})^* when n = \prod p_i^{k_i}, and the order of an element modulo n is the least common multiple of its orders modulo each prime power factor.[18] Thus, (\mathbb{Z}/n\mathbb{Z})^* is cyclic if and only if each component group is cyclic, which fails for $2^k with k \geq 3 or when multiple odd prime powers are present, as their exponent structures do not align to yield a single generator of full order \phi(n).[16] Explicit constructions of primitive roots for allowable composite moduli often involve lifting from lower powers via Hensel's lemma or direct adjustments. For prime powers p^k with odd prime p, if g is a primitive root modulo p^k, then g + t p^k for suitable t (0 to p-1) yields the primitive roots modulo p^{k+1} that are congruent to g modulo p^k; specifically, there are p-1 such t when k=1 and p such t when k \geq 2.[19] For forms like $2p^k, a primitive root modulo p^k can be adjusted (e.g., adding p^k if necessary to make it odd) to serve modulo $2p^k, combining via the Chinese Remainder Theorem.[16]Examples and Data
Specific Examples
A classic example of a primitive root occurs modulo 7, where \phi(7)=6 and the integer 3 generates the multiplicative group. To verify, compute the powers of 3 modulo 7: $3^1 \equiv 3, $3^2 \equiv 2, $3^3 \equiv 6, $3^4 \equiv 4, $3^5 \equiv 5, and $3^6 \equiv 1. Since the order is 6, matching \phi(7), 3 is primitive. Alternatively, confirm the order by checking that $3^{6/q} \not\equiv 1 \pmod{7} for each prime q dividing 6 (i.e., q=2,3): $3^3 \equiv 6 \not\equiv 1 and $3^2 \equiv 2 \not\equiv 1.[20][8] Modulo 9, where \phi(9)=6, the integer 2 serves as a primitive root. The powers are $2^1 \equiv 2, $2^2 \equiv 4, $2^3 \equiv 8, $2^4 \equiv 7, $2^5 \equiv 5, and $2^6 \equiv 1 \pmod{9}, yielding order 6. Checking against divisors: $2^3 \equiv 8 \not\equiv 1 and $2^2 \equiv 4 \not\equiv 1 \pmod{9}.[21] For modulo 14, with \phi(14)=6, 3 is again a primitive root. Compute: $3^1 \equiv 3, $3^2 \equiv 9, $3^3 \equiv 13, $3^4 \equiv 11, $3^5 \equiv 5, $3^6 \equiv 1 \pmod{14}. The order is 6, as $3^3 \equiv 13 \not\equiv 1 and $3^2 \equiv 9 \not\equiv 1 \pmod{14}.[22] Primitive roots do not exist for all n; consider modulo 8, where \phi(8)=4 but the unit group \{1,3,5,7\} has maximum order 2. For instance, $3^2 \equiv 1, $5^2 \equiv 1, and $7^2 \equiv 1 \pmod{8}, so no element achieves order 4.[23] Similarly, modulo 15 with \phi(15)=8, the maximum order is 4, as the group is isomorphic to C_4 \times C_2. Elements like 2 yield $2^4 \equiv 1 \pmod{15}, and 7 gives $7^4 \equiv 1 \pmod{15}, but no order reaches 8.[24]Table of Primitive Roots
The smallest primitive root modulo a prime p is the least positive integer g such that the multiplicative order of g modulo p is \phi(p) = p-1, where \phi denotes Euler's totient function.[25] For each such p, there are exactly \phi(p-1) primitive roots modulo p.[11] The following table lists the primes p \leq 200, their \phi(p), and the smallest primitive root g for each, based on verified computational data.[25]| p | \phi(p) | Smallest g |
|---|---|---|
| 2 | 1 | 1 |
| 3 | 2 | 2 |
| 5 | 4 | 2 |
| 7 | 6 | 3 |
| 11 | 10 | 2 |
| 13 | 12 | 2 |
| 17 | 16 | 3 |
| 19 | 18 | 2 |
| 23 | 22 | 5 |
| 29 | 28 | 2 |
| 31 | 30 | 3 |
| 37 | 36 | 2 |
| 41 | 40 | 6 |
| 43 | 42 | 3 |
| 47 | 46 | 5 |
| 53 | 52 | 2 |
| 59 | 58 | 2 |
| 61 | 60 | 2 |
| 67 | 66 | 2 |
| 71 | 70 | 7 |
| 73 | 72 | 5 |
| 79 | 78 | 3 |
| 83 | 82 | 2 |
| 89 | 88 | 3 |
| 97 | 96 | 5 |
| 101 | 100 | 2 |
| 103 | 102 | 5 |
| 107 | 106 | 2 |
| 109 | 108 | 6 |
| 113 | 112 | 3 |
| 127 | 126 | 3 |
| 131 | 130 | 2 |
| 137 | 136 | 3 |
| 139 | 138 | 2 |
| 149 | 148 | 2 |
| 151 | 150 | 6 |
| 157 | 156 | 5 |
| 163 | 162 | 2 |
| 167 | 166 | 5 |
| 173 | 172 | 2 |
| 179 | 178 | 2 |
| 181 | 180 | 2 |
| 191 | 190 | 19 |
| 193 | 192 | 5 |
| 197 | 196 | 2 |
| 199 | 198 | 3 |
| n | \phi(n) | Smallest g |
|---|---|---|
| 4 | 2 | 3 |
| 9 | 6 | 2 |
| 25 | 20 | 2 |
| 27 | 18 | 2 |
| 49 | 42 | 3 |