One residue whose powers are all of them

Necklaces that prove a theorem ends with a remark and moves on: the multiplicative order of a residue divides $p-1$, and that observation is the beginning of a subject. Here is the subject.

Fix a prime and take a residue that is not zero. Multiply it by itself repeatedly. The sequence must eventually repeat, and since multiplication by the residue can be undone, the first repeat is a return to the start — so the powers form a closed ring whose length is the residue’s order. Fermat’s theorem is the statement that the length divides $p-1$.

What Fermat’s theorem does not say #

The ring above has twelve beads and there are twelve residues, so the powers of two are all of them. That is a much stronger statement than the order divides twelve, and nothing in the necklace argument produces it.

To see the gap, take another base on the same modulus.

Five has order four. Four divides twelve, so the theorem holds, and the powers of five reach four residues out of twelve. A divisor of $p-1$ is not $p-1$, and a theorem that only bounds the order says nothing about whether anything achieves it.

A residue whose order is exactly $p-1$ is called a primitive root, and the claim that one always exists is a separate theorem. It is also a much more useful one: a primitive root turns multiplication into addition, since every residue is $g^k$ for exactly one $k$ between $0$ and $p-2$, and multiplying two residues adds their exponents. Everything multiplicative about the modulus becomes arithmetic on a single dial of $p-1$ positions — and a dial is the object numbers that wrap is about, so the theorem says one wrapping arithmetic sits inside another in a way the notation hides completely.

The count that forces one to exist #

The existence proof is a count, and it is the same kind of count an earlier essay runs — partition a set into classes of known size, and read a conclusion off the sizes.

The claim is: for every divisor $d$ of $p-1$, exactly $\varphi(d)$ residues have order $d$, where $\varphi$ counts the numbers up to $d$ sharing no factor with it. The last row of that table is $d = p-1$, and $\varphi$ of anything is at least one, so a residue of full order exists.

The argument has two halves and both are worth having, because the first is easy and the second is where the primality is spent.

At most $\varphi(d)$ residues have order $d$. Suppose one does, say $a$. Then the $d$ powers of $a$ all satisfy $x^d = 1$. A polynomial of degree $d$ over the residues modulo a prime has at most $d$ roots — this is where primality enters, and it fails badly for composites — so those $d$ powers are all the solutions of $x^d = 1$. Any residue of order $d$ satisfies that equation, so it is among the powers of $a$; and $a^k$ has order $d$ exactly when $k$ shares no factor with $d$. So there are either none of order $d$ or exactly $\varphi(d)$.

That first half is a genuine use of primality and it is worth isolating, because it is the only one. A polynomial of degree $d$ having at most $d$ roots is a statement that holds over any field and fails over the residues modulo a composite: $x^2 - 1$ has four roots modulo fifteen, so the bound is not a formality. The same fact settles how many solutions an equation can have over a finite field, and it is the reason the two subjects share their arithmetic.

And the totals leave no room for “none”. Every residue has some order, and every order divides $p-1$, so the counts over the divisors of $p-1$ must add to $p-1$. If any divisor contributed nothing, the total would fall short — because the totients of the divisors of $n$ already add to exactly $n$.

The identity underneath, which is not about primes #

The identity $\sum_{d \mid n} \varphi(d) = n$ is the load-bearing part, and its proof is a partition rather than a computation. Sort the numbers $1$ to $n$ by their greatest common divisor with $n$. The numbers whose greatest common divisor is $n/d$ are exactly the multiples of $n/d$ that share nothing else with $n$, and writing such a number as $(n/d)\cdot j$, the condition on $j$ is that it is at most $d$ and shares no factor with $d$. So that class has $\varphi(d)$ members.

Every number is in exactly one class, so the classes add to $n$. That is the whole proof, and nothing in it mentions primes — the identity is true for every $n$, which is worth noticing because it is the half of the existence argument that carries no hypothesis. The hypothesis is all in the polynomial-root bound above, and that is where the composite cases will break.

Counting one set in two ways is the most productive habit in this subject, and the shape here is the standard one: the left-hand side sorts by a property and adds up the classes, the right-hand side counts the whole thing directly, and the identity is the statement that both count the same set. Quadratic reciprocity is the same move on a much larger scale, and Fermat’s own theorem is it on a smaller one.

The other proof, which builds a generator out of pieces #

There is a second route to the same theorem and it is worth having, because it constructs rather than counts and because the tool it uses is needed again where the modulus is composite.

Start from a fact about combining orders, which is not the obvious one. If $a$ has order $m$ and $b$ has order $n$, the order of $ab$ is not generally $mn$, and it is not generally the least common multiple either — modulo thirteen, $2$ has order twelve and $2^{11}$ has order twelve, and their product is $2^{12}$, which is one on a dial of thirteen and so has order one. What is true is a restricted version: if $m$ and $n$ share no factor, then $ab$ has order exactly $mn$.

The proof of that is short. $(ab)^{mn} = 1$, so the order divides $mn$. Conversely, if $(ab)^k = 1$ then raising to the power $m$ kills $a$ and leaves $b^{km} = 1$, so $n$ divides $km$; since $n$ shares no factor with $m$ it divides $k$. The same argument the other way gives $m \mid k$, so $mn \mid k$. The coprimality is used exactly twice and the statement is false without it.

Now the construction. Let $\lambda$ be the largest order that occurs among the residues. Every order divides $\lambda$ — because if some residue had order $t$ not dividing $\lambda$, some prime power in $t$ would exceed the one in $\lambda$, and the combining fact above would build a residue of order larger than $\lambda$ out of suitable powers of the two. So every residue satisfies $x^{\lambda} = 1$, an equation of degree $\lambda$ with $p-1$ solutions, and the root bound forces $\lambda \ge p-1$. Since $\lambda$ divides $p-1$, it is $p-1$, and the residue achieving it is a generator.

Both proofs spend primality in the same place and nowhere else — the root bound — and they differ in what they hand over. The counting proof gives the exact number of residues of each order and no construction; this one gives a recipe for assembling a high-order element from lower-order ones and no count. Having both is what makes the composite case tractable, because $\lambda$ is a quantity in its own right and the argument above is the one that computes it when the modulus is not prime and $\lambda$ falls short.

The generators, and how many of them there are #

The table gives the count of generators for free: there are $\varphi(p-1)$ of them. Modulo thirteen that is $\varphi(12) = 4$, and the four are $2, 6, 7, 11$. Modulo seventeen it is $\varphi(16) = 8$, so half the residues generate.

Modulo eleven there are $\varphi(10) = 4$, and modulo the small primes the counts are $1, 1, 2, 2, 4, 4, 8, 6$ — a sequence that does not increase, because it depends on the factorisation of $p-1$ rather than on $p$.

The proportion is worth a moment because it is neither small nor predictable. $\varphi(p-1)/(p-1)$ can be as large as a half — when $p-1$ is twice a prime — and it can be pushed down towards nothing by choosing $p-1$ with many small prime factors, since each distinct prime factor $q$ multiplies the proportion by $1 - 1/q$. There are primes for which fewer than a fifth of the residues generate, and there is no upper bound on how small the fraction can be made.

Nothing in the existence proof locates a generator. The count says four exist modulo thirteen and gives no procedure for finding one beyond testing residues in turn, and testing a residue means computing its order. For a prime of several hundred digits, testing is feasible if the factorisation of $p-1$ is known — a residue is a generator exactly when $a^{(p-1)/q} \neq 1$ for every prime $q$ dividing $p-1$ — and is not feasible otherwise. So the theorem is an existence statement whose constructive version needs a factorisation, which is the standing shape of this subject.

There is a conjecture that sharpens the question and has been open since 1927. Artin conjectured that a fixed base that is not a perfect square and not $-1$ — two, say — is a primitive root for infinitely many primes, indeed for a positive proportion of them. It is unproved. What is known is due to Heath-Brown in 1986: at most two prime values of the base can fail, so at least one of $2$, $3$ and $5$ satisfies the conjecture and nobody can say which.

The dial the generator provides, and what lives on it #

Once a generator is fixed, every unit has an address: the exponent that reaches it. Writing the addresses out turns the multiplicative structure into an additive one, and several facts that are awkward in one language are immediate in the other.

The order of $g^k$ is $(p-1)/\gcd(k, p-1)$, which is the statement that the powers of $g^k$ are the multiples of $k$ on a dial of $p-1$ positions — and the multiples of $k$ on such a dial form a sub-dial whose size is $p-1$ divided by what $k$ and $p-1$ share. That single formula produces every count in the table above: the residues of order $d$ are the $g^k$ with $\gcd(k, p-1) = (p-1)/d$, and there are $\varphi(d)$ such $k$ by the same class-counting the identity above is about.

It also explains why the divisor structure of $p-1$ matters so much and the size of $p$ hardly at all. A prime with $p-1 = 2q$ for $q$ prime has only four divisors, so only four possible orders, and half its residues generate. A prime with $p-1$ highly composite has many orders and few generators. The arithmetic of the modulus has almost dropped out and been replaced by the arithmetic of $p-1$, which is the change of coordinates the generator performs.

The same relabelling is what makes the finite field with $p$ elements look like a familiar object: its non-zero elements are a single ring under multiplication, and every element is a power of one is that statement for the fields with $p^k$ elements as well, where the count of generators is $\varphi(p^k - 1)$ and the argument is the same one.

Where it fails, and the shape of the failure #

For a composite modulus the theorem usually fails, and the figure locates the exceptions rather than describing them. A generator exists modulo $n$ exactly when $n$ is $1$, $2$, $4$, a power of an odd prime, or twice one. Eight, twelve, fifteen, sixteen and twenty have none.

The reason is exactly the step the proof spent its primality on. Modulo fifteen the equation $x^2 = 1$ has four solutions — $1, 4, 11, 14$ — where a prime modulus permits at most two, and the four are what make a generator impossible: a generator’s powers would have to contain all four, but a cyclic ring has only one element of order two.

That failure is not a small exception. It means the units modulo a composite are generally not a single ring but a product of several, and the exponents no longer live on one dial. A later essay is about what replaces the dial, and about a consequence for primality testing that is more than a curiosity: the largest order of a unit modulo $n$ can be much smaller than the number of units, and a composite whose orders are all small is a composite that Fermat’s test cannot see.

What a generator is for #

Three uses, and each is the same observation applied differently.

Logarithms modulo a prime. Fix a generator $g$; then every residue is $g^k$ for a unique $k$, and $k$ is the discrete logarithm. Multiplication becomes addition of logarithms, exactly as it does for ordinary logarithms, and the tables that were used for hand computation modulo a prime were logarithm tables. Computing the logarithm in the other direction — given $g^k$, find $k$ — is believed to be hard, and a great deal of cryptography rests on the belief. The contrast with the exponentiation, which is a few hundred squarings, is what makes the asymmetry useful.

Deciding which residues are squares. Written as powers of a generator, the squares are exactly the even powers, so precisely half the residues are squares and the product of two non-squares is a square. Those facts are immediate from the ring and awkward from the definition, and they are what the reciprocity law is a law about.

Constructing things that need every residue once. A generator’s powers are a listing of the units with no repeats, which is what a sequence must be if it is to be used as a source of well-spread values. A linear congruential generator achieves a full period exactly when its multiplier plays the role of a generator for the relevant modulus, and the condition in that essay’s arithmetic is this theorem’s condition.

What the pictures cannot show #

Every figure here is drawn at a modulus below forty, and the interest of the subject is at moduli of hundreds of digits. The rings are drawn because a ring of twelve can be seen and a ring of $10^{600}$ cannot, and everything the drawings establish is the mechanism rather than the case.

The orders are computed by walking the orbit, which is the slowest possible method and the only one that needs no theory. At the sizes drawn it is instant and it is also the reason the figures are evidence: nothing consults a formula for an order, so a residue whose order failed to divide $p-1$ would be reported rather than assumed away.

And the ring’s layout carries no information. The residues are placed round the circle in numerical order because some order was needed, and the walk’s shape — a star, a polygon, a tangle — is an artefact of that choice. What is real is which residues the walk visits and how many steps it takes; the prettiness is not part of the mathematics, and a different placement would produce an unrecognisable picture of the same fact.

Still open: how often a fixed base generates #

The existence of a generator is settled and the behaviour of any particular base is not. Artin’s conjecture asks for the proportion of primes for which two is a generator and predicts a specific constant, about $0.3739558$, arrived at by treating the conditions at different primes as independent. The heuristic is convincing, the constant has been computed to many places, and the statement is unproved.

What is known is conditional in a way worth noting, because it is the standard situation in this subject. Hooley showed in 1967 that the conjecture follows from the generalised Riemann hypothesis, so the question is not isolated — it is attached to the central open problem about the distribution of primes, and a proof of that would settle this as a corollary.

The other direction is the one the figures are about. The count of residues of each order is exact and elementary, and it settles existence completely for prime moduli and, with more work, for all moduli. What it cannot do is tell anybody which residue to use, and the gap between knowing something exists and being able to produce it is unusually wide here: a prime of six hundred digits has plenty of generators and finding one requires factoring a six-hundred-digit number first.

What the two theorems are each worth #

Fermat’s theorem bounds and the existence theorem attains, and the difference between those two kinds of statement is worth carrying past this page.

A bound is cheap and it is what the necklace count gives: partition a set, read off a divisibility, done. Attainment needs more, and in this case it needed a fact about polynomials — that a prime modulus permits no more roots than the degree — which is a statement about the modulus rather than about counting. The extra hypothesis is visible in exactly the place where the theorem fails, which is the most satisfying way for a hypothesis to earn its place.

What the attained version buys is a change of coordinates. Once the residues are the powers of one of them, multiplication is addition, squares are even exponents, and the whole multiplicative structure is a single dial. That is a large return for one existence theorem, and it is the reason the subject bothers with primitive roots at all rather than stopping at the divisibility.

The pattern is worth naming because it recurs. A theorem that bounds a quantity usually comes from a partition — count something two ways and a divisibility falls out. A theorem that says the bound is achieved usually needs a second ingredient from somewhere else, and the second ingredient is what limits the theorem’s scope. Here the ingredient is a fact about polynomials, the scope is the moduli that are prime powers or twice one, and both the ingredient and the scope were invisible until somebody asked the stronger question.