A post about finite fields. Starts by proving the existence of finite fields and concludes by stating core results about their properties as Galois extensions.
I've found the basic theory of finite fields to be slippery. A month or two after I relearn it, I inevitably forget the order in which facts appear and are proven. I suspect this is partly because my main reference, Dummit and Foote, mixes results about finite fields in with broader topics of field and ring theory. If I was writing a textbook I'd do the same; but nonetheless, when you're drilling bookwork questions on finite fields specifically, it'd be nice to have all the facts in one place. This is my attempt to do just that.
My treatment isn't exhaustive, but it does cover the main points necessary to answer finite field questions on the UT Austin Algebra II prelim exam, I think.
Note: I haven't figured out a good way to achieve theorem numbering yet, which makes citing facts a little awkward. Instead, each theorem, lemma, proposition or corollary is cited as a link, and clicking said link will jump you to the point of the page where the cited fact first appears.
Before we begin we'll need two basic facts.
Proposition: Every field \(K\) has characteristic \(0\) or \(p\) for some prime number \(p\).
Proof: The characteristic \(n\in \mathbb Z\) of a field \(K\) is the unique nonnegative generator of \(\operatorname{ker}\varphi\) where \(\varphi\) is the unique map \(\varphi:\mathbb Z \to K\). This gives us an embedding \(\mathbb Z/(n) \to K\). Since \(K\) is a field, \(\mathbb Z/(n)\) must be a domain. This only occurs if \((n)\) is a prime ideal, giving us the result.
The following is a trivial (but important) corollary:
Corollary: Finite fields have prime characteristic.
We now prove a vital criterion for the separability of a polynomial: Proposition: Let \(K\) be a field. A polynomial \(f \in K[x]\) is separable if and only if \((f,f') = 1\) where \(f'\) is the formal derivative of \(f\).
Proof: Let \(L\) be the splitting field of \(f\) throughout. If \(f\) is inseparable then it has a repeated root in \(L\), and hence can be written
\[\begin{aligned}
f(x) = (x - \alpha)^2g(x)
\end{aligned}\]
for some \(g\in L[x]\) and \(\alpha \in L\). Then
\[\begin{aligned}
f'(x) = 2(x-\alpha)g(x) + (x-\alpha)^2g'(x),
\end{aligned}\]
which clearly has \(0\) as a root. Thus \(f'(x)\) and \(f(x)\) share a common factor and \((f,f')\neq 1\) as an ideal in \(L[x]\). Pulling back to \(K[x]\) under the inclusion \(K[x] \hookrightarrow L[x]\) demonstrates that \((f,f')\neq 1\) in \(K[x]\) too.
Suppose now that \((f, f') \neq 1\). This means that \(f\) and \(f'\) share a root \(\alpha\) in \(L\). Let \(f(x) = (x-\alpha)h(x)\) be a factorization of \(f\) in \(L\). Taking the derivative, we see
\[\begin{aligned}
f'(x) = h(x) - (x-\alpha)h'(x).
\end{aligned}\]
Since \(\alpha\) is a root of \(f'(x)\) by assumption, it must be the case that \(h\) is divisible by \((x-\alpha)\). This implies \(f\) is divisible by \((x-\alpha)^2\), hence it has a repeated root and is not separable.
Here we prove that finite fields exist and construct the field \(\mathbb F_{p^n}\) of order \(p^n\) as the splitting field of the polynomial \(x^{p^n}-x\), where \(p\) is the characteristic of the finite field and \(n\) is some positive integer. We begin with two lemmas. Lemma: If \(K\) is a finite field of prime characteristic \(p>0\), then \(|K| = p^n\) for some positive integer \(n\).
Proof: Since \(K\) has prime characteristic \(p\), there is a unique inclusion \(\mathbb F_p \hookrightarrow K\). Hence \(K\) is a finite extension of \(\mathbb F_p\), so \(K\) is an \(n\)-dimensional vector space with basis \(\mathbf b_1,...,\mathbf b_n\) over \(\mathbb F_p\) where \([K:\mathbb F_p] = n\). Every element in \(K\) can therefore be written uniquely as \(a_1\mathbf b_1 + ... + a_n\mathbf b_n\) with \(a_i \in \mathbb F_p\), giving us \(p^n\) elements in \(K\).
Lemma: If \(K\) is a field of prime characteristic \(p > 0\), then the polynomial \(f(x) = x^{p^n} - x\) is separable.
Proof: The derivative of \(f\) is \(f'(x) = p^{n}x^{p^n - 1} - 1 = -1\), so \((f,f') = 1\). By the Lemma above, \(f\) is separable.
From this Lemma we can immediately deduce the existence of finite fields. Proposition: (Existence of Finite Fields). Finite fields exist. Furthermore, if \(K\) is a finite field, then it has prime characteristic \(p\) for some \(p>0\) and is the splitting field of \(x^{p^n} - x\) over \(\mathbb F_p\) where \(n = [K:\mathbb F_p]\).
Proof: We prove the existence of finite fields by showing that the roots of \(f(x) = x^{p^n} - x\) form a field. With this in mind, let \(K\) be the splitting field of \(f\) over \(\mathbb F_p\). By the above
Lemma, \(f\) is separable over \(\mathbb F_p\) and hence has distint roots. Furthermore, \(0\) and \(1\) are roots of \(f\), and if \(\alpha\) and \(\beta\) are any other roots of \(f\), then \(\alpha^{p^n} = \alpha\) and \(\beta^{p^n} = \beta\) imply that \((\alpha\beta)^{p^n} = \alpha\beta\). This means
\[\begin{aligned}
f(\alpha\beta) = (\alpha\beta)^{p^n} - \alpha\beta = 0,
\end{aligned}\]
\[\begin{aligned}
$\alpha^{-1})^{p^n} = \alpha^{-1}$
\end{aligned}\]
and by the freshman's dream,
\[\begin{aligned}
f(\alpha + \beta)
&= (\alpha + \beta)^{p^n} - \alpha - \beta
= \alpha^{p^n} - \alpha + \beta^{p^n} - \beta = 0.
\end{aligned}\]
Thus the roots of \(f\) form a field, and since the splitting field \(K\) is the minimal field containing all roots of \(f\), it is precisely the \(p^n\) distinct roots of \(f\).
Now suppose that \(K\) is a finite field. Then it must be of order \(p^n\) by the above
Lemma. The group \(K^\times\) is then of order \(p^n-1\), meaning that for any nonzero element \(\alpha \in K\), \(\alpha^{p^n - 1} = 1\). This implies \(\alpha^{p^n} = \alpha\) for any element in \(K\), hence every element of \(K\) is a root of \(f(x) = x^{p^n} - x\). Since \(f\) can have at most \(p^n\) roots, \(K\) contains all the roots of \(f\) and is hence the splitting field of \(f\).
Since any two choices of a splitting field of a polynomial are isomorphic, any two finite fields of the same cardinality are isomorphic. This justifies the following remark:
Remark: We denote by \(\mathbb F_{p^n}\) the finite field of order \(p^n\).
In the last section we showed that finite fields exist and are all isomorphic to the splitting field of a separable polynomial over \(\mathbb F_p\); see the linked Proposition. We therefore obtain the following immediate Corollary:
Corollary: The extension \(\mathbb F_{p^n}/\mathbb F_p\) is a Galois extension.
Justification: Recall that \(L/K\) is a Galois extension if and only if \(L\) is the splitting field of a separable polynomial over \(K\).
It's Galois group has exceedingly nice structure; in fact, it is cyclic and generated by the Frobenius endomorphism \(F\).
Proposition: The Galois group \(\operatorname{GaL}(\mathbb F_{p^n}/\mathbb F)\) is cyclic and generated by the Frobenius endomorphism \(F:x \mapsto x^p\).
Proof: We first note that \(F\) is an automorphism of \(\mathbb F_{p^n}\) which fixes \(\mathbb F\). Indeed, it is injective since it is an endomorphism of fields and is hence also surjective by the finiteness of \(\mathbb F_{p^n}\). It fixes \(\mathbb F_p\) by Fermat's little theorem: \(\alpha^p = \alpha\) for all \(\alpha\in \mathbb F_p\).
Since \(F \in \operatorname{Gal}(\mathbb F_{p^n}/\mathbb F)\) and \(\operatorname{Gal}(\mathbb F_{p^n}/\mathbb F)| = [\mathbb F_{p^n}:\mathbb F_p] = n\), we know that \(F^n\) is the identity on \(\mathbb F_{p^n}\). We need only that \(n\) is the minimal such integer which makes this true. Suppose then that there were a positive integer \(d\) smaller than \(n\) such that \(F^d = \operatorname{id}\). Each \(\alpha \in \mathbb F_{p^n}\) would then satisfy \(\alpha^{p^d} = \alpha\), and hence the polynomial \(x^{p^d} - x\) would have \(p^n\) roots. This is impossible, so \(n\) must be the smallest positive integer such that \(F^n = \operatorname{id}\). We conclude that the Frobenius endomorphism generates of the Galois group of \(\mathbb F_{p^n}/\mathbb F_p\). .
Note that this means \(\operatorname{Gal}(\mathbb F_{p^n}/\mathbb F_n) = \mathbb Z/n\mathbb Z\). Quite a nice Galois group, all things considered. For one thing, it's Abelian, and hence all subextensions of \(\mathbb F_{p^n}/\mathbb F_p\) are Galois extensions of \(\mathbb F_p\) by the Fundamental Theorem. For another, we understand all the subgroups of \(\mathbb Z_n\mathbb Z\) – they're generated by integers \(d\) which divide \(n\) – and hence the subgroups of \(\operatorname{Gal}(\mathbb F_{p^n}/\mathbb F_p)\) are \(\langle F^d\rangle\) for integers \(d\) which divide \(n\) since \(F\) generates the Galois group. Hence for every divisor \(d\) of \(n\) there is exactly one subfield of \(\mathbb F_{p^n}\) over \(\mathbb F_p\) of order \(d\), namely the fixed field of the subgroup generated by \(F^{n/d}\), and it is isomorphic to \(\mathbb F_{p^d}\). The following theorem summarizes what we've shown thus far.
Theorem: Let \(K\) be a finite field of prime characteristic \(p>0\). Then
\(K\) is a finite extension of \(\mathbb F_{p}\)
\(K \cong \mathbb F_{p^n}\), where \(\mathbb F_{p^n}\) is the splitting field of \(x^{p^n} - x\) and \(n = [K:\mathbb F_p]\)
\(\mathbb F_{p^n}/\mathbb F_p\) is Galois of order \(n\) with cyclic Galois group generated by the Frobenius endomorphism
Every subextension of \(\mathbb F_{p^n}/\mathbb F_p\) is isomorphic to \(\mathbb F_{p^d}/\mathbb F_p\) for some \(d\) dividing \(n\).
Justification: See the paragraph immediately above this.
Given what we now know, we can retroactively construct \(\mathbb F_{p^n}\) as a simple extension of \(\mathbb F_p\). Doing this will yield some interesting results; for instance, we'll realize that \(x^{p^n} - x\) is actually the product of all irreducible polynomials of order \(d\) over \(\mathbb F_p\) with \(d\) varying over the divisors of \(n\).
To show that \(\mathbb F_{p^n}\) is a simple extension of \(\mathbb F_p\), we need to find an element of \(\mathbb F_{p^n}\) which is algebraic of order \(n\) over \(\mathbb F_p\).
Proposition: For each \(n\), there is an element \(\alpha \in \mathbb F_{p^n}\) of order \(n\) over \(\mathbb F_p\). Hence \(\mathbb F_{p^n} \cong \mathbb F_p(\alpha)\).
Proof: Fix some integer \(n\) and let \(\alpha\) be a generator of \(\mathbb F_{p^n}^\times\), noting that every finite subgroup of the multiplicative subgroup of
any field is cyclic (
see the below lemma). Then
\[\begin{aligned}
\mathbb F_{p^n} = \mathbb F^\times_{p^n} \cup \{0\} = \langle \alpha \rangle \cup \{0\} = \mathbb F_p(\alpha).
\end{aligned}\]
This proposition could also be stated as follows: for each integer \(n\), there is an irreducible polynomial of order \(n\) over \(\mathbb F_p\). Quotienting \(\mathbb F_p[x]\) by this irreducible polynomial would then produce a finite field of order \(p^n\) which, as we've seen, is necessarily \(\mathbb F_{p^n}\).
The following Lemma is included for completeness. It is Proposition 9.18 in Dummit and Foote.
Lemma: Let \(K\) be any field and let \(G\subseteq K^\times\) be a subgroup of \(K^\times\). If \(G\) is finite then it is cyclic.
Proof: The group \(K^\times\) is Abelian, hence so is \(G\). By the Structure Theorem of Abelian groups there exist integers \(n_1 ~|~ n_2 ~|~ ... ~|~ n_k\) such that
\[\begin{aligned}
G \cong \mathbb Z/n_1 \mathbb Z \times ... \times \mathbb Z/n_k \mathbb Z.
\end{aligned}\]
Since \(n_i ~|~ n_k\) for each \(1\leq i\leq k\), every element of \(G\) is a root of the polynomial \(x^{n_k} - 1\). If \(k > 1\), this would imply that there is a polynomial over \(K\) whose order is strictly less than the number of its roots, which is impossible. Hence \(k=1\) and we conclude that \(G\) is cyclic.
As a corollary to the Proposition from the previous section we obtain the following: Corollary: The polynomial \(x^{p^n} - x\) is the product of all irreducible polynomials of order \(d\) over \(\mathbb F_p\), where \(d\) ranges over the divisors of \(n\).
Proof: By
the linked Theorem we know \(\mathbb F_{p^n}\) contains a copy of \(\mathbb F_{p^d}\) for each \(d\) dividing \(n\), and hence also contains a primitive element \(\alpha_d\) of order \(d\). Since \(f(x) = x^{p^n} - x\) vanishes at \(\alpha_d\), the minimal polynomial of \(\alpha_d\) must divide \(x^{p^n} - x\).
Conversely, if \(g\) is an irreducible polynomial of order \(d\) dividing \(n\) with root \(\alpha\), then \(\mathbb F_p(\alpha)\cong \mathbb F_{p^d}\) is a subfield of \(\mathbb F_{p^n}\), and hence \(g\) divides \(x^{p^n} - x\).
Recall that a polynomial which is irreducible over \(\mathbb F_p\) for every prime is irreducible over \(\mathbb Q\). We end with an example which demonstrates the converse is not true.
Example: The polynomial \(x^4 + 1\) is irreducible over \(\mathbb Z\) but is reducible modulo every prime.
Solution: The polynomial \(x^4 + 1\) can easily be seen to be irreducible over \(\mathbb Z\) by applying Eisenstein to \((x+1)^4 + 1\). It is reducible module \(2\) since
\[\begin{aligned}
x^4 + 1 \equiv (x + 1)^4 \mod 2.
\end{aligned}\]
Suppose then that \(p\) is an odd prime. We'll argue that all the roots of \(x^4 + 1\) are in \(\mathbb F_{p^2}\), and since this is a degree 2 extension of \(\mathbb F_p\), it must be the case that \(x^4 + 1\) factors into (at least) quadratics over \(\mathbb F_p\). Notice first that \(p^2\) is either \(1\), \(3\), \(5\) or \(7\) modulo 8. All of these square to \(1\) in \(\mathbb Z/8\mathbb Z\); hence \(8 ~|~ p^2 - 1\). It is a general fact that \(d ~|~ n\) if and only if \(x^d - 1 ~|~ x^n - 1\), since
\[\begin{aligned}
d ~|~ n ~\iff ~ \text{every root of } ~x^d - 1 ~\text{ is a root of } ~x^n - 1 ~\iff x^d - 1 ~|~ x^n - 1,
\end{aligned}\]
and hence \(x^8 - 1\) divides \(x^{p^2 - 1} - 1\). This gives us the following divisibility chain:
\[\begin{aligned}
x^4 + 1 ~|~ x^8 - 1 ~|~ x^{p^2 - 1} - 1 ~|~ x^{p^2} - x,
\end{aligned}\]
which implies that \(x^4 + 1\) splits over \(\mathbb F_{p^2}\). Since \([\mathbb F_{p^2}:\mathbb F_p] = 2\), the roots of \(x^4 + 1\) are order \(2\) over \(\mathbb F_p\), implying \(x^4 + 1\) factors into quadratics modulo \(p\).
Here I complete some of the exercises in Section 14.3 of Dummit and Foote. Consider these to be examples.
Problem 1: Factor \(x^8 - x\) into irreducibles in \(\mathbb Z[x]\) and in \(\mathbb F_2[x]\).
Solution: Over \(\mathbb Z\) this polynomial factors as
\[\begin{aligned}
x^8 - x = x(x - 1)(x^6 + x^5 + x^4 + x^3 + x^2+ x+1).
\end{aligned}\]
The rightmost factor is the \(7\)th cyclotomic polynomial, and is hence irreducible over \(\mathbb Z\).
Over \(\mathbb F_2\), \(x^8 - x = x^{2^3} - x\) is the product of all irreducible polynomials of order either 1 or 3, since these are the two numbers dividing 3. Using the factorization we found above, we see that
\[\begin{aligned}
\frac{x^8 - x}{x(x-1)} = x^6 + x^5+x^4+x^3+x^2+x+1,
\end{aligned}\]
hence there are exactly 2 irreducible polynomials of order 3 over \(\mathbb F_2\). They both must have nonzero cubic and constant term, leaving only 4 options depending on whether or not \(x\) and \(x^2\) are present.
\(x^3 + x^2 + x + 1 = (x^2 + 1)(x + 1)\), hence it is not irreducible.
\(x^3 + 1\) has a root modulo \(\mathbb F_2\), hence is not irreducible. This implies \(x^3 + x^2 + 1\) and \(x^3 + x + 1\) are the two irreducible cubics over \(\mathbb F_2\), and hence
\[\begin{aligned}
x^8 - x = x(x - 1)(x^3 + x^2 + 1)(x^3 + x + 1) \mod 2
\end{aligned}\]
Problem 3: Prove that an algebraically closed field must be infinite.
Solution: Suppose \(K\) is an algebraically closed field. If \(K\) has characteristic \(0\), then it contains \(\mathbb Q\) and is hence infinite. If it is of prime characteristic \(p\) then it contains \(\mathbb F_p\). If \(K\) were finite, then \([K:\mathbb F_p] = n\) for some integer \(n\). However, it must then be the case that \(x^{p^{n+1}} - x\) doesn't factor into linear terms over \(K\), as this would imply \([K:\mathbb F_p] = n+1\). Hence \(K\) must be infinite.