Every element is a power of one of them

A finite field’s addition is dull: $k$ independent copies of the integers modulo a prime, and nothing more to say. Its multiplication is not.

The claim #

Take a finite field with $q$ elements and throw away the zero. What is left is $q-1$ elements, closed under multiplication, each with a reciprocal — a group.

That group is always a single cycle. There is an element $g$ such that

$$g^0,\ g^1,\ g^2,\ \dots,\ g^{q-2}$$

are all $q-1$ of the non-zero elements, each exactly once, and $g^{q-1} = 1$.

Such a $g$ is called a primitive element. The figure above shows one for $GF(16)$: the powers of $\alpha$ march around the wheel, produce every non-zero element on the way, and close.

This is not obvious, and it is not true in every finite group of the same shape. It is a consequence of the field structure and it fails immediately if the field is replaced by a ring.

What it buys #

Once a primitive element is fixed, every non-zero element has a discrete logarithm: the exponent $i$ with $g^i = z$.

Then multiplying is adding:

$$g^a \cdot g^b = g^{a+b \bmod (q-1)}.$$

The whole $q \times q$ multiplication table collapses to a table of $q-1$ exponents plus one addition. In $GF(256)$ that is the difference between sixty-five thousand entries and two tables of two hundred and fifty-five, which is why every implementation of byte arithmetic in the world uses logarithms.

The figure checks that rule rather than announcing it: for every ordered pair of non-zero elements it computes the product in the field, looks up its exponent, and requires it to be the sum of the two exponents modulo $q-1$. Two hundred and twenty-five pairs in $GF(16)$, all of them.

That reduction of multiplication to addition is the same manoeuvre as an ordinary logarithm, and the resemblance is not superficial: both turn a group into the integers by naming a generator and counting how far along it each element sits.

The two tables, in practice #

It is worth spelling out how the reduction is actually used, because it is one of the few places where a piece of pure algebra is implemented literally and unchanged.

Fix a primitive element. Build two arrays of length $q-1$: log, mapping each non-zero element to its exponent, and exp, mapping each exponent back to its element. Then

$$a \cdot b = \text{exp}\big[(\text{log}[a] + \text{log}[b]) \bmod (q-1)\big],$$

and division is the same with a minus sign. Two lookups, an addition and one more lookup, with the case $a = 0$ or $b = 0$ handled separately because zero has no logarithm.

In $GF(256)$ the two arrays are two hundred and fifty-five bytes each. The alternative — a full multiplication table — is sixty-five thousand bytes, and in 1970s hardware that was the difference between fitting and not.

The single awkwardness is the exception for zero, and it is worth noticing that it is unavoidable rather than an artefact. Zero is not in the multiplicative group at all; the group is what is left after removing it. Every convenience on this page is a convenience about that group, and zero has to be handled by hand precisely because it is the one element with no reciprocal.

How many primitive elements there are #

Not every element is primitive. In $GF(16)$ the element $\alpha^3$ has order five, because $(\alpha^3)^5 = \alpha^{15} = 1$, and its powers reach only five of the fifteen.

The count is exactly $\varphi(q-1)$, where $\varphi$ is Euler’s totient: $g^k$ generates the whole cycle precisely when $k$ shares no factor with $q-1$, since otherwise $g^k$ has smaller order.

The figures compute that count twice. Once by the formula, from the factorisation of $q-1$; and once by brute force, taking each of the $q-1$ elements in turn, listing its powers, and counting how many produce the whole group. In $GF(16)$ both give $8$ out of $15$; in $GF(8)$ both give $6$ out of $7$; in $GF(9)$ both give $4$ out of $8$.

Why it is true #

The proof is a counting argument and it uses the field property exactly once, in a place worth watching.

Let $m = q-1$ be the size of the group. For each divisor $d$ of $m$, ask how many elements have order exactly $d$.

The key step: the equation $z^d = 1$ has at most $d$ solutions, because it is a polynomial equation of degree $d$ over a field and a polynomial cannot have more roots than its degree. That is the only place the field is used, and it is where the argument would collapse over a ring with zero divisors.

Now suppose some element has order exactly $d$. Its $d$ powers are all distinct and all satisfy $z^d = 1$, so they are all the solutions. Among those $d$ powers, the ones of order exactly $d$ are the $\varphi(d)$ whose exponent is coprime to $d$.

So for each $d$ the number of elements of order $d$ is either $0$ or $\varphi(d)$. Summing over divisors:

$$m = \sum_{d \mid m} (\text{elements of order } d) \le \sum_{d \mid m} \varphi(d) = m,$$

the last equality being the standard identity that the totients of the divisors of $m$ add up to $m$. Equality throughout forces every term to be $\varphi(d)$ rather than $0$ — including $d = m$ itself.

So there are $\varphi(m)$ elements of order $m$, and in particular at least one. The group is cyclic.

The identity used at the last step deserves its own look, since it is doing real work. That $\sum_{d \mid m}\varphi(d) = m$ is itself a counting argument of the kind this collection likes: classify the $m$ fractions $\frac{1}{m}, \frac{2}{m}, \dots, \frac{m}{m}$ by the denominator each has in lowest terms. A fraction reducing to denominator $d$ has a numerator coprime to $d$, so there are $\varphi(d)$ of them, and every fraction is counted once. The same $m$ objects, sorted two ways.

Every subgroup, and only those #

A second consequence is worth stating because it is what makes the structure so rigid.

In a cyclic group of size $m$, there is exactly one subgroup of each size dividing $m$ and none of any other size. The subgroup of size $d$ is the set of powers $g^{m/d}, g^{2m/d}, \dots$ — evenly spaced points around the wheel.

So the subfields and subgroups of a finite field are completely determined by the arithmetic of divisors, with no choices anywhere. $GF(16)$ contains $GF(4)$ and $GF(2)$ and nothing else, because $4$ and $2$ divide $16$ as powers of two, while $GF(8)$ contains $GF(2)$ only, since $3$ does not divide $4$ but $1$ divides $3$.

That rigidity is the reason a great deal of the theory can be done by counting divisors rather than by construction. Nothing has to be searched for; the divisor lattice already says what is there.

Where it fails, and the failure is instructive #

Drop the field and the theorem goes with it.

Take the integers modulo $8$ and keep the units — the residues with reciprocals, namely $1, 3, 5, 7$. That is a group of order four under multiplication. But

$$3^2 = 9 \equiv 1,\qquad 5^2 = 25 \equiv 1,\qquad 7^2 = 49 \equiv 1,$$

so every element squares to $1$ and nothing has order four. The group is not a cycle.

The proof above breaks at exactly the point predicted: $z^2 = 1$ has four solutions in a ring of degree-two polynomials’ worth of room, because $\mathbb{Z}/8$ is not a field and a quadratic may have four roots there.

That is a good test of whether the argument was understood. The conclusion is not about groups of order $q-1$ in general; it is about the multiplicative group of a field, and every step used it.

The same wheel over the integers #

For a prime $p$ the field is just the integers modulo $p$, and the theorem becomes a classical statement: there is a residue whose powers run through all of $1, \dots, p-1$. Such a residue is called a primitive root modulo $p$.

The existence proof is the counting argument above and gives no hint of which residue works. Finding one means testing candidates, and there is no formula: $2$ is a primitive root modulo $5$ and modulo $11$, and is not modulo $7$ or $17$.

Whether a fixed number is a primitive root infinitely often is an open question. Artin conjectured in 1927 that $2$ is a primitive root for infinitely many primes — indeed for a definite proportion of them, about $37.4\%$ — and it is still unproved for any single specific base. It is known that at least one of $2$, $3$ and $5$ works infinitely often, which is a peculiar state of knowledge to be in: a theorem that one of three statements is true, with no way to say which.

That gap between existence and identification is the same one running through this whole field. The counting argument produces a primitive element without producing it, exactly as the counting argument for large graphs produces a colouring nobody can exhibit. What is proved is that the search will succeed, not where.

Fermat, generalised for nothing #

One corollary falls out with no extra work and it is a familiar theorem in unfamiliar clothes.

Since the group has $q-1$ elements, every element’s order divides $q-1$ by Lagrange’s theorem, so

$$z^{q-1} = 1 \quad\text{for every non-zero } z,$$

and therefore $z^q = z$ for every element including zero.

For $q$ prime that is Fermat’s little theorem, which this collection has already proved by counting necklaces. Here it arrives as a statement about the size of a group, valid over every finite field rather than only over the integers modulo a prime, and it costs one line.

The two proofs are worth comparing. The necklace argument is combinatorial and shows why the theorem is true in a way that can be looked at. This one shows that the theorem was never about primes — it is about a finite group having a size — and generalises without effort. Neither is better; they answer different questions.

There is a second corollary of the same kind, and it explains a construction from the first anchor of this field. Since $z^q = z$ holds for every element, the polynomial $z^q - z$ has all $q$ elements of the field as roots, and it has degree $q$, so it factors completely:

$$z^q - z = \prod_{c \in F} (z - c).$$

Every finite field is therefore the complete set of roots of one polynomial, which is a very tidy way for an object to be described and is the starting point of the uniqueness theorem the previous essay quoted. Two fields of the same size are the root sets of the same polynomial, and a relabelling between them is available for that reason.

That identity also gives the fastest test for whether a polynomial is irreducible over $GF(p)$, and hence the fastest way to build the fields in the first place, which closes a small loop: the construction needs an irreducible polynomial, and the object built supplies the test for finding one.

The map that is easy one way #

There is an asymmetry in the logarithm that has to be mentioned and that this field will not develop.

Computing $g^i$ from $i$ is a matter of repeated squaring: about $\log_2 i$ multiplications, and short. Recovering $i$ from $g^i$ — the discrete logarithm proper — has no comparably direct formula, and in a large field nobody knows a quick way to do it.

That asymmetry is the foundation of a great deal of cryptography, and it is a question about cost: how much work a procedure takes as the field grows. Cost is not this field’s subject and no essay here states a running time or names a machine; another site in this fleet owns computation read as cost, and the question belongs there.

What belongs here is the structural fact, which is complete on its own terms: the map $i \mapsto g^i$ is a bijection from the integers modulo $q-1$ onto the non-zero elements of the field, carrying addition to multiplication. That statement is proved above and takes no position on how hard either direction is to compute.

What the wheel is a picture of #

A word about the figure, because the drawing makes a choice that is worth defending.

The non-zero elements have no natural order. They are not numbers, they do not increase, and any arrangement of them on a page is imposed. The wheel imposes one: the order in which the powers of $g$ produce them.

That ordering is not arbitrary and it is not a presentational convenience. It is the structure the essay is about — the claim that a single element’s powers exhaust the group is exactly the claim that this arrangement exists — so drawing the elements in that order and closing the loop is drawing the theorem.

What the picture cannot show is that the arrangement is forced. A different primitive element gives a different wheel, with the same elements in a different cyclic order, and both are correct. The invariant content is the length of the cycle and the fact that some element achieves it; the particular sequence is a choice, like the choice of which irreducible polynomial builds the field.

Where this anchor ends #

Two essays have established what a finite field is and how it is put together: prime powers only, one field per size, addition a stack of copies of $GF(p)$, multiplication a single cycle.

That is the arithmetic the whole of this field’s coding theory was written in, and it is also the arithmetic behind the finite geometries that come next. The projective plane with seven points is built from $GF(2)$, the one with thirteen points from $GF(3)$, and the pair of orthogonal squares that Euler could not find at order six exists at every prime power for the same reason: a field of that size exists, and a field is enough.