How often two generates every remainder

One residue whose powers are all of them proved that every prime $p$ has a primitive root: a number whose powers, taken modulo $p$, run through all $p - 1$ non-zero remainders before they repeat. It proved more: there are exactly $\varphi(p - 1)$ of them. It did not say which numbers they are, and in particular it did not say whether $2$ is one.

Sometimes it is and sometimes it is not. Modulo $11$ the powers of $2$ are $2, 4, 8, 5, 10, 9, 7, 3, 6, 1$, every remainder once: $2$ is a primitive root. Modulo $7$ they are $2, 4, 1$ and round again, stuck in a cycle of three: it is not. The question this essay measures is how often — for what share of the primes is $2$ a primitive root — and the answer is a constant that nobody has been able to prove is right.

Among the $148{,}932$ primes up to two million, $2$ is a primitive root for $37.43\%$. The running share in the figure wanders among the first few thousand primes and then settles, and the line it settles on was drawn in 1927 by Emil Artin, from an argument about independent accidents.

A question Gauss asked about decimals #

The question is older than Artin and began with long division. The decimal expansion of $1/p$ repeats with a period equal to the order of $10$ modulo $p$ — the number of steps before the remainders of the division repeat — so $1/p$ has the longest possible period, $p - 1$ digits, exactly when $10$ is a primitive root modulo $p$. $1/7 = 0.\overline{142857}$ has period six; $1/17$ has period sixteen; $1/11 = 0.\overline{09}$ has period two.

Carl Friedrich Gauss tabulated such periods in his Disquisitiones Arithmeticae of 1801 and asked whether infinitely many primes have the full period. That is the question for the base $10$, and the base changes nothing essential. For the base $2$ it asks how often a binary fraction $1/p$ has the full period, or equivalently how often a shift register of a certain kind cycles through every state. The answer, measured, is a little over three primes in eight, for either base.

Stuck in a smaller cycle #

The powers of $2$ modulo $p$ form a cycle whose length — the order of $2$ — divides $p - 1$, by Fermat’s theorem. The powers miss some remainders exactly when the order is a proper divisor of $p - 1$, and that happens exactly when, for some prime $q$ dividing $p - 1$, the power $2^{(p-1)/q}$ is already $1$.

That last condition has a meaning: $2^{(p-1)/q} \equiv 1$ says that $2$ is a $q$-th power modulo $p$ — that some number, raised to the $q$-th power, leaves the same remainder as $2$. So $2$ fails to be a primitive root modulo $p$ exactly when there is a prime $q$ dividing $p - 1$ for which $2$ is a $q$-th power modulo $p$. For $q = 2$ that is the familiar question of whether $2$ is a square, a quadratic residue, which the supplements to reciprocity answer: it is, exactly when $p$ leaves $1$ or $7$ on division by $8$.

Artin’s product #

Artin’s argument treats each of these obstructions as an accident with a definite chance.

For a prime $q$, two things must happen for $q$ to spoil $2$. First, $q$ must divide $p - 1$; among the primes, by Dirichlet’s theorem on primes in arithmetic progressions, that happens for a share $1/(q - 1)$ of them. Second, given that, $2$ must be one of the $q$-th powers, which are a fraction $1/q$ of the non-zero remainders; if $2$ behaves like a typical remainder, that has chance $1/q$. So the chance that $q$ spoils $2$ is $1/(q(q - 1))$, and if the accidents for different $q$ are independent, the chance that none of them happens is

$$A = \prod_{q \text{ prime}} \left(1 - \frac{1}{q(q-1)}\right) = 0.3739558\ldots,$$

Artin’s constant. The first factor, for $q = 2$, is $\tfrac12$; the second, for $q = 3$, is $\tfrac56$; the factors approach one quickly, and the product converges to about three in eight. The figure computes it over the primes up to two hundred thousand, with an estimate of the rest, and draws it as the dashed line the measured share settles onto.

The argument is a heuristic, not a proof, and it has two soft spots. It assumes $2$ is a “typical” remainder for the purposes of being a $q$-th power, and it assumes the accidents for different $q$ are independent. For the base $2$ both assumptions turn out to be harmless — the measured share agrees with $A$ to the precision two million allows. For other bases, one of them fails.

Eight bases, and the one that is different #

For most bases the measured share is near $37.4\%$: $3$, $6$, $7$, $10$ and $11$ all sit on Artin’s constant within the fluctuation two million primes allow. The base $5$ does not. It is a primitive root for $39.36\%$ of the primes, well outside any reasonable fluctuation, and $13$ is slightly high too.

The discrepancy was discovered exactly this way. In 1957 Derrick Henry Lehmer and Emma Lehmer computed, on one of the first electronic computers, how often small bases were primitive roots, and found that some did not match Artin’s constant. Hans Heilbronn found the reason, and Artin accepted the correction: for a base whose squarefree part $a$ leaves $1$ on division by $4$, the density is not $A$ but

$$A \left(1 - \mu(a) \prod_{q \mid a} \frac{1}{q^2 - q - 1}\right),$$

which for $a = 5$ is $A \cdot \tfrac{20}{19} = 0.3936\ldots$ — the measured $39.36\%$ to four figures. The figure computes the corrected prediction and the measurement independently, and they agree for every base drawn.

Drawn together, the two bases make the correction visible. Both running shares wander among the small primes, and both settle — but onto different lines, two percentage points apart, which by two million primes is many times the size of the fluctuation. The gap does not close as more primes are counted, which is what distinguishes a wrong constant from a slow convergence, and the corrected constant for $5$ sits exactly where its curve settles.

Two accidents that are one #

The reason is that, for the base $5$, the accidents for $q = 2$ and $q = 5$ are not independent.

For $5$ to be a fifth power modulo $p$, the prime $5$ must divide $p - 1$, so $p$ leaves $1$ on division by $5$. And by quadratic reciprocity, $5$ is a square modulo $p$ exactly when $p$ is a square modulo $5$ — which a prime leaving $1$ certainly is. So whenever $5$ is a fifth power, it is also a square. The figure counts: $5$ is a square for half the primes, a fifth power for about one in twenty, and both for the same one in twenty, where independence would predict one in forty.

Artin’s product counted the two ways for $5$ to fail as if they could happen separately, and so subtracted their overlap as if it were small. It is total, so fewer primes are lost than the product says, and $5$ is a primitive root more often. The base $5$ is entangled with the quadratic field built from $\sqrt 5$, which lives inside the field built from fifth roots of unity, and every base whose squarefree part leaves $1$ on division by $4$ has the same kind of entanglement with its own square root. Bases like $2$, $3$ and $10$ have none, and for them the independence Artin assumed is true.

How much the powers miss #

A primitive root misses nothing. When $2$ is not one, its powers miss a fraction of the remainders, and the index — $p - 1$ divided by the order — measures how many times over.

The index is $1$ for $37.4\%$ of the primes, $2$ for $28.0\%$, $3$ for $6.6\%$, and smaller shares after that — but not in a steadily falling pattern. Even indices are commoner than odd ones of similar size, because the factor $2$ in the index is decided by whether $2$ is a square, which is decided by $p$ modulo $8$, and that is not an independent accident either. Each index has its own density, given by its own Artin-type product with its own corrections, and every index occurs for a positive share of the primes if the corresponding heuristics are right.

The smallest primitive root #

A companion question asks not how often a given number works but how soon one does: for each prime, what is the smallest primitive root?

Among the primes up to two million, $2$ is the smallest primitive root for $55{,}744$ of them — the same $37.43\%$, since whenever $2$ works it is the smallest candidate. After that come $3$ for $33{,}758$ primes, $5$ for $20{,}717$, then $7$, $6$ and $11$. The average smallest primitive root over all $148{,}932$ primes is $4.89$, and the largest in the range is $73$, needed for the prime $760{,}321$. Primitive roots are almost always tiny, and the Artin-type densities explain why: each small number has a fixed chance of working, the chances do not fall to zero, and so the first success comes quickly.

What can be proved about the worst case is far weaker than what is seen. David Burgess’s estimates show that the smallest primitive root is at most about $p^{1/4}$, times a slowly growing factor; under the generalised Riemann hypothesis Victor Shoup showed it is at most a power of $\log p$. The truth, as far as computation can tell, is closer to $\log p$ itself — and no method comes near proving it.

Where a generator of every remainder is useful #

Primitive roots are not only a curiosity of number theory; they are the working part of several constructions that need to visit every remainder once.

A multiplicative congruential generator — multiply by $g$ and reduce modulo a prime $p$ at every step — cycles through all $p - 1$ non-zero remainders exactly when $g$ is a primitive root, which is the longest period such a generator can have. The planes a recurrence cannot leave showed what else such a generator’s output does, and choosing its multiplier starts with choosing a primitive root. The Diffie–Hellman key exchange, the first public-key method, publishes a large prime and a primitive root, and relies on the difficulty of recovering an exponent from a power. And the Welch construction of Costas arrays — patterns of dots used in radar and sonar, with no two displacement vectors equal — places a dot in row $g^i$ of column $i$ for a primitive root $g$, which works because the powers of a primitive root never repeat within a period.

In each case the question “is $g$ a primitive root?” is answered by factoring $p - 1$ and checking the $q$-th powers, exactly as the figures do. And in each case the density measured here is why finding one is quick: trying $2$, $3$, $5$, … finds a primitive root within a handful of attempts for almost every prime.

What is proved #

The heuristic has been turned into a theorem in two ways, neither complete.

Christopher Hooley proved in 1967 that Artin’s conjecture, with Heilbronn’s correction, is true if the generalised Riemann hypothesis holds — the statement about the zeros of the functions that count primes in arithmetic progressions and in the fields generated by roots of unity and roots of $a$. The hypothesis supplies exactly what the heuristic assumed: that the primes spread evenly enough over the conditions “$q$ divides $p - 1$ and $a$ is a $q$-th power” that the inclusion–exclusion over all $q$ converges to the product. Counting what has no formula described the ordinary Riemann hypothesis as a statement about how evenly the primes are spread; Hooley’s proof needs that evenness in infinitely many number fields at once.

Without the hypothesis, much less is known. Rajiv Gupta and Ram Murty showed in 1984 that some specific base is a primitive root for infinitely many primes, and Roger Heath-Brown sharpened their method in 1986 to show that at least one of 2, 3 and 5 is a primitive root for infinitely many primes. In fact the theorem shows that at most two prime numbers can fail to be primitive roots for infinitely many primes — but it cannot say which two, and so it cannot name a single number that is known, unconditionally, to be a primitive root for infinitely many primes.

Why the question matters for proving primes #

The two ways of recognising a prime that the neighbouring essays describe differ in whether they need a primitive root, and Artin’s question sits exactly on the difference.

Lucas’s test, the basis of the certificates in an order that proves a prime, proves $n$ prime by exhibiting a number whose order modulo $n$ is $n - 1$ — a primitive root. Its practical speed rests on finding one quickly, and the densities here are why that works: a small base succeeds for a fixed share of primes, so a few tries suffice. The test of the row that proves a prime needs no primitive root at all; it checks a polynomial identity that every prime satisfies. That independence from Artin’s question is part of why its correctness could be proved unconditionally while a deterministic version of Lucas’s test, which would need a guaranteed small primitive root, still leans on the Riemann hypothesis. The same necklace count that gives Fermat’s theorem underlies both; they part company over whether a single number must be found that does all the work.

What two million primes cannot settle #

The figures measure; they prove nothing about infinity. A share of $37.43\%$ among the primes up to two million is compatible with the true density being $A$, and equally compatible with the share drifting slowly elsewhere at astronomically large primes. The agreement with $A$ to four figures is strong evidence and no more.

Every primitive-root test is exact. For each prime, $p - 1$ is factored completely by a table of smallest prime factors, and $a$ is declared a primitive root only after $a^{(p-1)/q} \neq 1$ has been checked for every prime $q$ dividing $p - 1$; no orbit is walked and no rounding is involved.

The fluctuation band is a statistician’s, not a number theorist’s. The figures accept a measured share as agreeing with a prediction when it is within four standard deviations of a coin-tossing model, which treats primes as independent trials. They are not independent, and the band is a yardstick for the eye rather than a statement about primes.

Still open: whether 2 works infinitely often #

Is $2$ a primitive root modulo infinitely many primes? Every computation says it is, for three primes in eight; Hooley’s theorem says it is if the generalised Riemann hypothesis holds; Heath-Brown’s says that $2$, $3$ or $5$ is. Unconditionally, for $2$ itself, it is not known — not the density, not even that the set of such primes is infinite.

The obstacle is the one an order that proves a prime ran into in its closing question. Showing that $2$ is a primitive root for infinitely many primes means controlling, for large primes $q$, how many primes $p$ have $q$ dividing $p - 1$ and $2$ a $q$-th power — primes in progressions with enormous moduli — and that control is exactly what the Riemann hypothesis would provide and what no other method has yet delivered.

Accidents that are not independent #

The habit worth keeping is how the prediction was repaired.

Artin’s constant came from treating each way for $2$ to fail as a separate accident with its own chance, and multiplying. That is the natural first model of any arithmetic property, and for $2$ it is right. For $5$ it is wrong, and the error was not in the chances but in the independence: two of the accidents were the same accident, tied together by quadratic reciprocity. A product of probabilities is only as good as the independence behind it, and the corrections to Artin’s conjecture are a catalogue of the hidden dependences among primes — each one a piece of algebraic number theory that the naive count did not know it needed.