Finite Fields

Introduction

A finite field is a field with finitely many elements, and the theory is unusually complete: for every prime power $q = p^n$ there is exactly one field with $q$ elements, up to isomorphism, and there are no others. The additive structure is that of a vector space over the prime field $\mathbb{F}_p$, and the multiplicative structure is that of a cyclic group, two facts that together determine the theory.

The finite fields are the base case on which much of the arithmetic of this category is tested, and they are the natural first examples of Galois extensions, of perfect fields, and of fields with a nontrivial automorphism group. This article constructs $\mathbb{F}_q$, proves existence and uniqueness, studies the Frobenius automorphism, shows that $\mathbb{F}_q^\times$ is cyclic, and determines the subfield lattice.

Throughout, $p$ is a prime, $q = p^n$ with $n \geq 1$, and $\mathbb{F}_p = \mathbb{Z}/p\mathbb{Z}$ is the prime field of characteristic $p$. The general theory of extensions, splitting fields, separability and algebraic closures is from Field Extensions and Splitting Fields and Algebraic Closure. All finite fields are commutative; the noncommutative finite division rings are classified by Wedderburn's theorem, mentioned at the end, but they are not the subject here.

---

Prime Fields and Characteristic

Definition. The prime field of a field $K$ is the intersection of all its subfields, equivalently the subfield generated by $1$.

Theorem. Every field $K$ has a prime field isomorphic to $\mathbb{Q}$ if $\operatorname{char} K = 0$ and to $\mathbb{F}_p$ if $\operatorname{char} K = p$. In particular a finite field has characteristic $p > 0$ and contains $\mathbb{F}_p$.

Proof. The unique ring homomorphism $\mathbb{Z} \to K$ has kernel $0$ or $(p)$ for a prime $p$, by Fields, §3. In the first case it extends to an embedding $\mathbb{Q} \to K$, whose image is the smallest subfield. In the second it induces an embedding $\mathbb{F}_p \to K$, and the image is the smallest subfield. A finite field cannot contain $\mathbb{Q}$, since $\mathbb{Q}$ is infinite.

Proposition. Let $K$ be a finite field. Then $\lvert K \rvert = p^n$, where $p = \operatorname{char} K$ and $n = [K:\mathbb{F}_p]$.

Proof. The prime field $\mathbb{F}_p$ is a subfield of $K$, and $K$ is a vector space over it. If $[K:\mathbb{F}_p] = n < \infty$ then $\lvert K \rvert = p^n$, and $K$ is finite precisely when this degree is finite.

---

Existence and Uniqueness of $\mathbb{F}_{p^n}$

Construction

Theorem. For every prime power $q = p^n$ there exists a field with $q$ elements, namely the splitting field of

$$ f_q(x) = x^{q} - x $$

over $\mathbb{F}_p$.

Proof. Let $K$ be the splitting field of $f_q$ over $\mathbb{F}_p$. First, $f_q$ has no repeated root: its derivative is $f_q'(x) = q x^{q-1} - 1 = -1$ in characteristic $p$, since $q = p^n$ is divisible by $p$; hence $\gcd(f_q, f_q') = 1$ and $f_q$ is separable. The roots of $f_q$ in $K$ form a subfield:

• if $\alpha^q = \alpha$ and $\beta^q = \beta$, then $(\alpha \pm \beta)^q = \alpha^q \pm \beta^q = \alpha \pm \beta$ by the freshman's dream, since the binomial coefficients $\binom{q}{k}$ are divisible by $p$ for $0 < k < q$;
• $(\alpha\beta)^q = \alpha^q \beta^q = \alpha\beta$, and $(\alpha^{-1})^q = (\alpha^q)^{-1} = \alpha^{-1}$ for $\alpha \neq 0$.

So the roots form a subfield of $K$ containing $\mathbb{F}_p$; since $K$ is generated over $\mathbb{F}_p$ by the roots, $K$ equals that subfield and consists exactly of the $q$ distinct roots of $f_q$. Hence $\lvert K \rvert = q$.

Definition. The field with $q = p^n$ elements is written $\mathbb{F}_q$ or $\mathbb{F}_{p^n}$, and is called the Galois field of order $q$.

Uniqueness

Theorem. Any two fields with $q = p^n$ elements are isomorphic. Moreover, every finite field has $p^n$ elements for some prime $p$ and some $n \geq 1$.

Proof. Let $K$ be a field with $q$ elements. Then $\operatorname{char} K = p$ for a prime $p$ and $K \supseteq \mathbb{F}_p$, with $q = p^n$ and $n = [K:\mathbb{F}_p]$. The multiplicative group $K^\times$ has order $q - 1$, so every $\alpha \in K^\times$ satisfies $\alpha^{q-1} = 1$ by Lagrange's theorem and hence $\alpha^q = \alpha$; the same holds for $\alpha = 0$. Thus every element of $K$ is a root of $x^q - x$, and since $x^q - x$ has at most $q$ roots, $K$ is exactly the set of its roots. Therefore $K$ is a splitting field of $x^q - x$ over $\mathbb{F}_p$, and splitting fields of a polynomial are unique up to isomorphism fixing $\mathbb{F}_p$.

Remark. The uniqueness is strong enough that one writes the field $\mathbb{F}_q$ with $q$ elements. Note that $\mathbb{Z}/4\mathbb{Z}$ is not a field: $2 \cdot 2 = 0$. The additive group of $\mathbb{F}_{p^n}$ is isomorphic to $(\mathbb{Z}/p\mathbb{Z})^n$, which is not cyclic for $n \geq 2$, while the multiplicative structure is cyclic, as shown below.

---

The Frobenius Automorphism

Definition and Properties

Theorem (Frobenius). Let $K$ be a field of characteristic $p > 0$. The map

$$ \varphi : K \to K, \qquad \varphi(x) = x^p, $$

is an injective field endomorphism, called the Frobenius map. If $K$ is finite, $\varphi$ is an automorphism, of order $\log_p \lvert K \rvert$ when $K = \mathbb{F}_{p^n}$.

Proof. Additivity is the freshman's dream: $(x + y)^p = x^p + y^p$, since the intermediate binomial coefficients $\binom{p}{k}$ are divisible by $p$ for $0 < k < p$. Multiplicativity is immediate, and $\varphi(1) = 1$. The kernel is $0$, since $x^p = 0$ forces $x = 0$, so $\varphi$ is injective; an injective map from a finite set to itself is bijective, so $\varphi$ is an automorphism when $K$ is finite. On $\mathbb{F}_{p^n}$, $\varphi^n(x) = x^{p^n} = x$ for all $x$, since every element satisfies $x^{p^n} = x$; and $\varphi^k \neq \mathrm{id}$ for $0 < k < n$, because if $\varphi^k$ were the identity then every element of $\mathbb{F}_{p^n}$ would satisfy $x^{p^k} = x$, so all $p^n$ elements of the field would be roots of the polynomial $x^{p^k} - x$ of degree $p^k < p^n$, which is impossible. Hence the order is exactly $n$.

Corollary. For each divisor $d$ of $n$ the fixed field of $\varphi^d$ in $\mathbb{F}_{p^n}$ is $\mathbb{F}_{p^{d}}$; in particular the fixed field of $\varphi$ is $\mathbb{F}_p$.

Proof. The fixed field of $\varphi^d$ consists of the elements $x$ with $x^{p^d} = x$, a set of at most $p^d$ elements, and it contains $\mathbb{F}_{p^d}$ since every element of $\mathbb{F}_{p^d}$ satisfies $x^{p^d} = x$. Hence it has at least $p^d$ and at most $p^d$ elements, so it equals $\mathbb{F}_{p^d}$.

The Galois Group

Theorem. The automorphism group $\operatorname{Aut}(\mathbb{F}_{p^n}/\mathbb{F}_p)$ is cyclic of order $n$, generated by the Frobenius automorphism $\varphi$. Consequently $\mathbb{F}_{p^n}/\mathbb{F}_p$ is a Galois extension of degree $n$.

Proof. The extension $\mathbb{F}_{p^n}/\mathbb{F}_p$ is separable, because $\mathbb{F}_{p^n}$ is finite and hence perfect, so by the counting theorem of Splitting Fields and Algebraic Closure the number of $\mathbb{F}_p$-embeddings of $\mathbb{F}_{p^n}$ into an algebraic closure equals the degree $n$, and every such embedding is an automorphism of the finite field. The powers $\varphi^0, \varphi^1, \ldots, \varphi^{n-1}$ are $n$ distinct $\mathbb{F}_p$-automorphisms by the order computation above, so $\operatorname{Aut}(\mathbb{F}_{p^n}/\mathbb{F}_p) = \langle \varphi \rangle$ is cyclic of order $n$, and $\mathbb{F}_{p^n}/\mathbb{F}_p$ is Galois of degree $n$.

The Frobenius automorphism acts on an element $\alpha$ by the cycle

$$ \alpha \mapsto \alpha^p \mapsto \alpha^{p^2} \mapsto \cdots \mapsto \alpha^{p^{d-1}} \mapsto \alpha^{p^d} = \alpha, $$

where $d$ is the degree of $\alpha$ over $\mathbb{F}_p$; the elements $\alpha^{p^i}$ for $0 \leq i < d$ are the conjugates of $\alpha$ over $\mathbb{F}_p$ and are exactly the roots of $m_\alpha$, which is therefore separable and has all its roots in $\mathbb{F}_{p^n}$ when $d \mid n$.

---

The Multiplicative Group

Cyclicity

Theorem. The multiplicative group of a finite field is cyclic. Consequently $\mathbb{F}_q^\times \cong \mathbb{Z}/(q-1)\mathbb{Z}$.

This is a special case of the general fact that every finite subgroup of the multiplicative group of a field is cyclic.

Theorem. Let $K$ be a field and let $G \leq K^\times$ be a finite subgroup of order $m$. Then $G$ is cyclic.

Proof. Let $e$ be the exponent of the finite abelian group $G$, so $e \mid m$ and $e$ is the least common multiple of the orders of the elements of $G$. Every element of $G$ satisfies $x^e = 1$, so every element of $G$ is a root of $x^e - 1$. A polynomial of degree $e$ has at most $e$ roots in the field $K$, so $m \leq e$. Since always $e \mid m$, we get $e = m$. A finite abelian group whose exponent equals its order is cyclic, by the structure theorem for finite abelian groups. Hence $G$ is cyclic.

Corollary. $\mathbb{F}_q^\times$ is cyclic of order $q - 1$; a generator is called a primitive element of $\mathbb{F}_q$.

Primitive Elements and Primitive Polynomials

Definition. An element $\gamma \in \mathbb{F}_q^\times$ is primitive if it generates the cyclic group $\mathbb{F}_q^\times$. The minimal polynomial of a primitive element is a primitive polynomial over $\mathbb{F}_p$.

Theorem. Let $q = p^n$. The number of primitive elements of $\mathbb{F}_q$ is $\varphi(q - 1)$, where $\varphi$ is the Euler totient function; the number of monic primitive polynomials of degree $n$ over $\mathbb{F}_p$ is $\varphi(q-1)/n$.

Proof. The generators of the cyclic group of order $q - 1$ are exactly the $\gamma^k$ with $\gcd(k, q-1) = 1$, so there are $\varphi(q-1)$ of them. Each monic primitive polynomial of degree $n$ has exactly $n$ roots in $\mathbb{F}_q$, namely the conjugates of a primitive element under the Frobenius, and the sets of roots of distinct such polynomials are disjoint, partitioning the $\varphi(q-1)$ primitive elements into classes of size $n$.

Corollary (number of irreducibles). The number of monic irreducible polynomials of degree $n$ over $\mathbb{F}_p$ is

$$ \frac{1}{n} \sum_{d \mid n} \mu(d)\, p^{n/d}, $$

where $\mu$ is the Möbius function. Each is the minimal polynomial of an element of $\mathbb{F}_{p^n}$ of degree $n$ over $\mathbb{F}_p$, and the formula counts the Frobenius orbits of size $n$.

Proof. Let $d$ be the degree of $\alpha \in \mathbb{F}_{p^n}$ over $\mathbb{F}_p$. Then $d \mid n$, the element $\alpha$ lies in $\mathbb{F}_{p^d}$ and in no proper subfield of it, and $m_\alpha$ has degree equal to the size of the Frobenius orbit of $\alpha$, so the elements of degree $d$ are exactly those counted by the Möbius inversion. Counting the $p^n$ elements of $\mathbb{F}_{p^n}$ by the degrees of their minimal polynomials gives the formula.

Example. Over $\mathbb{F}_2$ the monic irreducible polynomial $x^2 + x + 1$ is primitive: its roots have order $3 = 2^2 - 1$. Over $\mathbb{F}_3$ the polynomial $x^2 + 1$ is irreducible but not primitive: a root $i$ satisfies $i^2 = -1 = 2$, so $i^4 = 1$ and $i$ has order $4 < 8$; the primitive quadratic polynomials over $\mathbb{F}_3$ are $x^2 + x + 2$ and $x^2 + 2x + 2$, in agreement with $\varphi(8)/2 = 2$.

---

Subfields

The Subfield Criterion

Theorem. Let $m, n \geq 1$. Then $\mathbb{F}_{p^m}$ is a subfield of $\mathbb{F}_{p^n}$ if and only if $m \mid n$. When this holds the subfield is unique, and $[\,\mathbb{F}_{p^n} : \mathbb{F}_{p^m}\,] = n/m$.

Proof. Suppose $\mathbb{F}_{p^m} \subseteq \mathbb{F}_{p^n}$. The degree is multiplicative over the tower $\mathbb{F}_p \subseteq \mathbb{F}_{p^m} \subseteq \mathbb{F}_{p^n}$, so $n = m \cdot [\,\mathbb{F}_{p^n}:\mathbb{F}_{p^m}\,]$ and $m \mid n$.

Conversely, suppose $m \mid n$. Since $p^m - 1$ divides $p^n - 1$, the polynomial $x^{p^m-1} - 1$ divides $x^{p^n-1} - 1$, so $x^{p^m} - x$ divides $x^{p^n} - x$ in $\mathbb{F}_p[x]$. All roots of $x^{p^m} - x$ lie in $\mathbb{F}_{p^n}$, since they are roots of $x^{p^n} - x$, whose root set is $\mathbb{F}_{p^n}$. These roots form the subfield $\mathbb{F}_{p^m}$ by the argument of the construction theorem. Uniqueness: a subfield with $p^m$ elements is a field of that order, unique up to isomorphism inside its algebraic closure. The degree is $n/m$ by the tower law.

Corollary. The subfields of $\mathbb{F}_{p^n}$ correspond bijectively to the divisors of $n$, and form a lattice isomorphic to the divisor lattice: $\mathbb{F}_{p^{m_1}} \cap \mathbb{F}_{p^{m_2}} = \mathbb{F}_{p^{\gcd(m_1,m_2)}}$ and the compositum inside $\mathbb{F}_{p^n}$ is $\mathbb{F}_{p^{\operatorname{lcm}(m_1,m_2)}}$.

Proof. The first identity follows since the intersection has $p^{\gcd}$ elements by the criterion; the second since the compositum is the smallest subfield containing both, hence corresponds to the least common multiple.

Example. The subfields of $\mathbb{F}_{2^{12}}$ correspond to the divisors of $12$, namely

with $\mathbb{F}_4 \cap \mathbb{F}_8 = \mathbb{F}_2$ since $\gcd(2,3) = 1$, and $\mathbb{F}_4 \mathbb{F}_8 = \mathbb{F}_{64}$ since $\operatorname{lcm}(2,3) = 6$.

---

Explicit Constructions

Small Fields

Example ($\mathbb{F}_4$). The polynomial $x^2 + x + 1$ is irreducible over $\mathbb{F}_2$ (it has no root, as $1^2 + 1 + 1 = 1$ and $0 + 0 + 1 = 1$). Put $\mathbb{F}_4 = \mathbb{F}_2[x]/(x^2+x+1)$ and let $\omega$ be the class of $x$, so $\omega^2 = \omega + 1$. Then

$$ \mathbb{F}_4 = \{0, 1, \omega, \omega + 1\} = \{0, 1, \omega, \omega^2\}, \qquad \omega^3 = 1, $$

and $\omega$ is primitive. The Frobenius map is $\varphi(\omega) = \omega^2 = \omega + 1$, so $\operatorname{Gal}(\mathbb{F}_4/\mathbb{F}_2) = \{1, \varphi\} \cong \mathbb{Z}/2\mathbb{Z}$. The only irreducible quadratic over $\mathbb{F}_2$ is $x^2+x+1$, consistent with $\varphi(3)/2 = 1$.

Example ($\mathbb{F}_8$). The polynomial $x^3 + x + 1$ is irreducible over $\mathbb{F}_2$. Put $\mathbb{F}_8 = \mathbb{F}_2[x]/(x^3+x+1)$ and let $\alpha$ be the class of $x$, so $\alpha^3 = \alpha + 1$. Then the powers of $\alpha$ enumerate the nonzero elements:

and $\alpha^7 = 1$, so $\alpha$ is primitive. The Frobenius automorphism has order $3$: it fixes $0$ and $1$ and permutes the remaining six elements in the two orbits of size $3$

$$ \{\alpha, \alpha^2, \alpha^2+\alpha\}, \qquad \{\alpha+1, \alpha^2+1, \alpha^2+\alpha+1\}, $$

which are the root sets of the two monic irreducible cubics $x^3+x+1$ and $x^3+x^2+1$.

Example ($\mathbb{F}_9$). The polynomial $x^2 + 1$ is irreducible over $\mathbb{F}_3$, since $2$ is not a square modulo $3$. Put $\mathbb{F}_9 = \mathbb{F}_3[x]/(x^2+1)$ and let $i$ be the class of $x$, so $i^2 = -1 = 2$. The element $i$ has order $4$, since $i^2 = 2$, $i^4 = 1$; it is not primitive. The element $1 + i$ is primitive:

$$ (1+i)^2 = 1 + 2i + i^2 = 2i, \qquad (1+i)^4 = (2i)^2 = 4 i^2 = 4 \cdot 2 = 8 \equiv 2 \equiv -1 \pmod 3, $$

so $(1+i)^8 = 1$ and the order is $8 = 9 - 1$. The minimal polynomial of $1+i$ is $(x - (1+i))(x - (1-i)) = x^2 + x + 2$, which is primitive, and $x^2 + x + 2$ and $x^2 + 2x + 2$ are the two primitive quadratics over $\mathbb{F}_3$.

Conjugates and Frobenius Orbits

Proposition. Let $\alpha \in \mathbb{F}_{p^n}$ have degree $d$ over $\mathbb{F}_p$, and let $m_\alpha$ be its minimal polynomial. Then $d \mid n$, the roots of $m_\alpha$ are $\alpha, \alpha^p, \ldots, \alpha^{p^{d-1}}$, and they are distinct.

Proof. The extension $\mathbb{F}_p(\alpha)/\mathbb{F}_p$ has degree $d$ and sits inside $\mathbb{F}_{p^n}$, so $d \mid n$ by the tower law. The Frobenius map $\varphi$ fixes $\mathbb{F}_p$, so if $m_\alpha(\alpha) = 0$ then $0 = \varphi(m_\alpha(\alpha)) = m_\alpha(\alpha^p)$; iterating, each $\alpha^{p^i}$ is a root of $m_\alpha$. The orbit closes at the first $d$ with $\alpha^{p^d} = \alpha$, which is the degree of $\alpha$ over $\mathbb{F}_p$. Distinctness holds because $\varphi$ is injective: if $\alpha^{p^i} = \alpha^{p^j}$ with $0 \leq i < j < d$, then $\alpha^{p^{j-i}} = \alpha$ and the degree of $\alpha$ is at most $j - i < d$, a contradiction.

Remark (Wedderburn's theorem). Every finite division ring is a field. Thus there is no noncommutative analogue of $\mathbb{F}_q$: the finite structures in this category are all commutative. The proof is standard and is not needed for the commutative theory developed here.

---

Summary

A finite field has $p^n$ elements for a prime $p$ and an integer $n \geq 1$, with prime field $\mathbb{F}_p$, and for each prime power $q = p^n$ there is exactly one field $\mathbb{F}_q$ with $q$ elements, up to isomorphism: it is the splitting field of $x^q - x$ over $\mathbb{F}_p$, and the roots of $x^q - x$ are exactly the elements of $\mathbb{F}_q$. The Frobenius map $\varphi(x) = x^p$ is an automorphism of $\mathbb{F}_{p^n}$ of order $n$, its fixed field is $\mathbb{F}_p$, and $\operatorname{Aut}(\mathbb{F}_{p^n}/\mathbb{F}_p)$ is cyclic of order $n$, generated by $\varphi$; the Frobenius orbits on an element are its conjugates, the roots of its minimal polynomial.

The multiplicative group $\mathbb{F}_q^\times$ is cyclic of order $q - 1$, since every finite subgroup of the multiplicative group of a field is cyclic; its generators are the primitive elements, of which there are $\varphi(q-1)$, and the primitive polynomials of degree $n$ over $\mathbb{F}_p$ number $\varphi(p^n-1)/n$. The subfields of $\mathbb{F}_{p^n}$ are exactly the fields $\mathbb{F}_{p^m}$ with $m \mid n$, each occurring once, and they form a lattice isomorphic to the divisor lattice of $n$ under intersection and compositum. Every finite field is perfect and every extension of finite fields is separable, cyclic and hence Galois.

Summary of Notation

Further Reading

• E. H. Moore, "A doubly-infinite system of simple groups", Proceedings of the Chicago Congress of Mathematics (1896), for the original existence and uniqueness theorem for finite fields.
• Rudolf Lidl and Harald Niederreiter, Finite Fields (Cambridge University Press, 2nd ed. 1997), for the standard reference: constructions, primitive polynomials and the subfield lattice.
• Serge Lang, Algebra (Springer, 3rd ed. 2002), for cyclicity of finite subgroups of fields and the structure of $\overline{\mathbb{F}_p}$.
• David S. Dummit and Richard M. Foote, Abstract Algebra (Wiley, 3rd ed. 2004), for explicit constructions of $\mathbb{F}_4$, $\mathbb{F}_8$, $\mathbb{F}_9$ and the counting of irreducibles.
• Joseph L. Dornhoff and Franz E. Hohn, Applied Modern Algebra (Macmillan, 1978), for the Möbius inversion count of irreducible polynomials.
• Leonard E. Dickson, Linear Groups with an Exposition of the Galois Field Theory (Teubner, 1901), for the classical development of finite field arithmetic.