Artin's conjecture on primitive roots
Artin's conjecture on primitive roots is a famous unsolved problem in number theory, proposed by Emil Artin in 1927, which asserts that for any integer a that is neither -1 nor a perfect square, there exist infinitely many prime numbers p such that a is a primitive root modulo p.[1] A primitive root modulo p is an integer whose powers generate all nonzero residues modulo p, meaning the multiplicative order of a modulo p is exactly p-1.[2] The conjecture originated from Artin's observations on the distribution of primitive roots and was inspired by earlier work, including computations by Derrick Henry Lehmer in 1957 that supported the idea through numerical evidence.[3] In addition to infinitude, Artin conjectured a quantitative version specifying the natural density of such primes p, predicted to be a positive proportion given by a formula involving Artin's constant A \approx 0.3739558136, defined as the infinite product A = \prod_p \left(1 - \frac{1}{p(p-1)}\right) over all primes p.[4] For a specific a, the density is A adjusted by a factor depending on the prime factors of a, reflecting the heuristic assumption that the conditions for a to be a primitive root—namely, that a^{(p-1)/q} \not\equiv 1 \pmod{p} for each prime q dividing p-1—are independent for different q.[5] This heuristic leads to the product form and has been verified computationally for small a, though dependencies arise for certain residue classes of a, such as when a \equiv 1 \pmod{4}.[6] While the conjecture remains unproven unconditionally, significant progress has been made. In 1967, Christopher Hooley established it under the assumption of the Generalized Riemann Hypothesis (GRH), proving not only infinitude but also the asymptotic density \delta(a) \frac{x}{\log x} + O\left( \frac{x \log \log x}{\log^2 x} \right) for the count of such primes up to x.[7] Unconditionally, D. R. Heath-Brown showed in 1986 that the conjecture holds for all integers a except at most two prime exceptions, meaning there are at most two primes q for which q is a primitive root modulo only finitely many p.[8] This implies, for instance, that at least one of 2, 3, or 5 is a primitive root modulo infinitely many primes.[9] Further extensions include average versions over a and results in function fields, but the full unconditional resolution for fixed a persists as a major open challenge.[6]Background Concepts
Primitive Roots Modulo a Prime
In number theory, for a prime number p > 2, the multiplicative group (\mathbb{Z}/p\mathbb{Z})^* consists of the integers from 1 to p-1 under multiplication modulo p, forming a cyclic group of order p-1.[10] This cyclicity implies that the group is generated by a single element, allowing the residues to be expressed as powers of that generator.[11] An integer g is called a primitive root modulo the prime p if it generates (\mathbb{Z}/p\mathbb{Z})^*, meaning the multiplicative order of g modulo p is exactly p-1.[2] In other words, the powers of g modulo p produce all nonzero residues exactly once before repeating.[12] The concept of primitive roots was introduced by Carl Friedrich Gauss in his 1801 work Disquisitiones Arithmeticae, specifically in Article 57, where he attributed the term to Leonhard Euler.[13] Primitive roots exist modulo p if and only if p = 2 or p is an odd prime, as the cyclic nature of the group guarantees the presence of generators in these cases.[14] For example, 2 is a primitive root modulo 5, since its powers modulo 5 are $2^1 \equiv 2, $2^2 \equiv 4, $2^3 \equiv 3, and $2^4 \equiv 1, cycling through all elements of (\mathbb{Z}/5\mathbb{Z})^*.[12]Multiplicative Order
In number theory, the multiplicative order of an integer a modulo a prime p, denoted \operatorname{ord}_p(a), is defined as the smallest positive integer k such that a^k \equiv 1 \pmod{p}, provided that \gcd(a, p) = 1.[15] This order exists because the multiplicative group (\mathbb{Z}/p\mathbb{Z})^\times is finite, ensuring that the powers of a eventually cycle back to 1 by the pigeonhole principle.[10] A fundamental property is that \operatorname{ord}_p(a) divides p-1, the order of the group (\mathbb{Z}/p\mathbb{Z})^\times, which follows directly from Fermat's Little Theorem stating that a^{p-1} \equiv 1 \pmod{p}.[15] Consequently, the powers of a modulo p generate a cyclic subgroup of (\mathbb{Z}/p\mathbb{Z})^\times of order exactly \operatorname{ord}_p(a), and since this group is cyclic of order p-1, the maximal possible order is p-1.[10] An element a achieves this maximal order if and only if it is a primitive root modulo p, as defined in the context of generators for the full group.[15] To determine \operatorname{ord}_p(a), factor p-1 into its prime factors p-1 = q_1^{e_1} \cdots q_r^{e_r}, and compute the order as (p-1) divided by the largest integer m such that a^{(p-1)/m} \equiv 1 \pmod{p}; practically, this involves checking the minimal exponents where a^{(p-1)/q_i^j} \equiv 1 \pmod{p} for each prime power dividing p-1.[](https://users.fmf.uni-lj.si/lavric/Rosen%20-%20Elementary%20number%20 theory%20and%20its%20applications.pdf) For illustration, consider p = 7 and a = 3: the powers are $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 \pmod{7}, so \operatorname{ord}_7(3) = 6 = 7-1, confirming 3 is a primitive root modulo 7.Formulation of the Conjecture
Statement
Artin's conjecture on primitive roots asserts that for any integer a that is neither -1 nor a perfect square, the set S(a) = \{ p \text{ prime} : p \nmid a \text{ and } a \text{ is a primitive root modulo } p \} is infinite. This means there are infinitely many primes p such that the multiplicative order of a modulo p equals p-1, generating the full multiplicative group (\mathbb{Z}/p\mathbb{Z})^\times. The integer a = -1 is excluded because its order modulo any odd prime p > 2 is 2, which divides p-1 but cannot equal p-1 > 2. Similarly, if a is a perfect square, say a = b^2, then by Fermat's Little Theorem, a^{(p-1)/2} \equiv 1 \pmod{p}, so the order of a divides (p-1)/2 and thus cannot be p-1. The conjecture further claims that the natural density of S(a) exists and is positive. For eligible a, this density is a positive rational multiple of Artin's constant C \approx 0.3739558136, defined as the infinite product C = \prod_q (1 - 1/(q(q-1))) over all primes q, with the multiple depending on the prime factors of a and, for perfect powers a = b^h with h > 1 odd, further adjustments based on the primes dividing h. For example, for a=2, the density is exactly C. The conjecture was proposed by Emil Artin in a letter to Helmut Hasse dated September 27, 1927. As of 2025, the infinitude part remains unproven unconditionally for any fixed eligible a.[5]Artin's Constant
Artin's constant, denoted C, is the conjectured natural density of the set of primes p for which a fixed integer a (neither -1 nor a perfect square) serves as a primitive root modulo p. This constant emerges from a heuristic calculation of the average proportion of primitive roots in the multiplicative group modulo p, averaged over primes p. The proportion of primitive roots modulo p is \phi(p-1)/(p-1), where \phi is Euler's totient function. To obtain the density, one models the prime factors of p-1 as occurring independently with probability $1/q for each prime q, but more precisely uses Dirichlet densities for the events p \equiv 1 \pmod{q}. For each prime q > 2, the density of primes p with q \mid p-1 (i.e., p \equiv 1 \pmod{q}) is $1/(q-1). Conditional on this, the probability that a^{(p-1)/q} \equiv 1 \pmod{p} (the condition failing primitivity for that q) is $1/q, as it places a in the unique cyclic subgroup of index q. The "bad" probability for q is thus $1/[q(q-1)]. Assuming independence across distinct primes q, inclusion-exclusion yields the survival probability (density of primes where no such bad event occurs) as the infinite product over these local factors. For q=2, the bad probability is $1/2, corresponding to a being a quadratic residue modulo p. The formula for Artin's constant is C = \prod_{p\ \prime} \left(1 - \frac{1}{p(p-1)}\right). This product was first derived and numerically approximated by Emil Artin in his 1927 letter to Helmut Hasse. It converges to approximately 0.3739558136, with high-precision values such as 0.37395581361920250 obtained via expressions involving Riemann zeta function values at even integers. For specific integers a, the conjectured density equals exactly C when there are no local adjustments, such as for a = 2. For other suitable a, the density is C multiplied by the adjustment factor \prod_{\substack{q\ \prime \\ q \mid a \\ q>2}} \frac{q-2}{q-1}, accounting for altered Galois action in cyclotomic extensions when odd primes divide a. For a that are higher odd powers, additional factors apply based on the exponent. The Euler product form of C bears analogy to densities in sieve theory, such as the proportion of square-free integers \prod_p (1-1/p^2)^{-1} or the average order of \phi(n)/n = \prod_p (1-1/p), but here encodes the intertwined probabilities of splitting in cyclotomic fields and subgroup membership.Examples
Primitive Roots for Small Integers
Artin's conjecture posits that for small integers a neither equal to -1 nor a perfect square, there exist infinitely many primes p (not dividing a) such that a is a primitive root modulo p. Empirical evidence supporting this for specific small a comes from explicit computations of the sets S(a) = \{ p \text{ prime} : a \text{ is a primitive root modulo } p \}, which reveal numerous such primes without any indication of finiteness.[16] For a = 2, the set S(2) begins with the primes 3, 5, 11, 13, 19, 29, 37, 53, 59, 61, 67, 83, 101, 107, and 131, among others.[17] These primes demonstrate that 2 generates the multiplicative group modulo p, as its order is exactly p-1. No counterexamples—primes where 2 fails to be a primitive root in a manner suggesting the set is finite—have been observed in extensive checks. Similar patterns hold for a = 3 and a = 5. For a = 3, S(3) includes 5, 7, 17, 19, 29, 31, 43, 53, 79, 89, 101, 113, 127, 137, and 139 (excluding the trivial case p=2).[18] For a = 5, S(5) comprises 7, 17, 23, 37, 43, 47, 53, 73, 83, 97, 103, 107, 113, 137, and 157 (excluding small primes 2 and 3 where the notion is degenerate).[19] In each case, the initial members align with the conjecture's expectation of positive density. The following table lists the first 15 primes in S(a) for a = 2, 3, 5:| a | Primes in S(a) |
|---|---|
| 2 | 3, 5, 11, 13, 19, 29, 37, 53, 59, 61, 67, 83, 101, 107, 131 |
| 3 | 5, 7, 17, 19, 29, 31, 43, 53, 79, 89, 101, 113, 127, 137, 139 |
| 5 | 7, 17, 23, 37, 43, 47, 53, 73, 83, 97, 103, 107, 113, 137, 157 |
Density Illustrations
Numerical illustrations of the conjectured densities in Artin's conjecture can be obtained by computing the proportion of primes up to a given limit for which a fixed integer a is a primitive root. These empirical proportions provide evidence supporting the heuristic, showing alignment with the expected densities derived from Artin's constant C ≈ 0.3739558. For a = 2, the proportion of primes p < 106 for which 2 is a primitive root is approximately 0.374, closely matching C.[17] This computation is based on the sequence of such primes, which has been tabulated extensively.[17] For a = 8, the conjectured density is adjusted to (3/5)C ≈ 0.224 due to the power structure of 8. Counts among the first 105 primes yield a proportion of approximately 0.223, demonstrating good agreement.[21] For exceptional values like a = 17, where no exceptional prime divides the order adjustment, the conjectured density is C. Empirical ratios up to large limits remain approximately 0.374, consistent with the heuristic.[17] To visualize trends, consider the proportion |S(a) ∩ [1, x]| / π(x) plotted against log log x for a = 2 and a = 3. Computations reveal initial oscillations in the proportions, but they suggest convergence toward the predicted densities as x increases. Extensive verifications up to 1018 show no discrepancies with the conjecture.[6] The following table summarizes key empirical proportions for selected a:| a | Limit (x or number of primes) | Empirical proportion | Conjectured density |
|---|---|---|---|
| 2 | p < 106 | ≈ 0.374 | C ≈ 0.374 |
| 8 | First 105 primes | ≈ 0.223 | (3/5)C ≈ 0.224 |
| 17 | Up to large N | ≈ 0.374 | C ≈ 0.374 |