Finite Fields

Proof:

The binomial theorem \[ (a + b)^p = \sum_{k=0}^{p} \binom{p}{k} a^k b^{p-k} \] holds in any commutative ring, since its usual proof by induction on the exponent uses only the ring axioms and the commutativity of multiplication. For \(0 \lt k \lt p\) the integer \(\binom{p}{k}\) is divisible by \(p\). Indeed, \(p! = \binom{p}{k} \, k! \, (p - k)!\), and in the field \(\mathbb{Z}_p\) (\(\mathbb{Z}_p\) is a Field) the product \(k! \, (p - k)!\) of the nonzero residues \(1, 2, \ldots, p - 1\) is nonzero, so \(p! \equiv 0\) forces \(\binom{p}{k} \equiv 0 \pmod p\). Since \(R\) has characteristic \(p\), every term with \(0 \lt k \lt p\) vanishes, and \((a + b)^p = a^p + b^p\).

The case of general \(n\) follows by induction. If \((a + b)^{p^{n-1}} = a^{p^{n-1}} + b^{p^{n-1}}\), then \[ \begin{align*} (a + b)^{p^n} &= \bigl((a + b)^{p^{n-1}}\bigr)^p \\\\ &= \bigl(a^{p^{n-1}} + b^{p^{n-1}}\bigr)^p \\\\ &= a^{p^n} + b^{p^n}. \end{align*} \] For the difference, apply the sum formula to \(a = (a - b) + b\) to get \(a^{p^n} = (a - b)^{p^n} + b^{p^n}\), and rearrange. Finally, \(x \mapsto x^{p^n}\) preserves products because \(R\) is commutative and sends \(1\) to \(1\), so it is a ring homomorphism.

Proof Sketch:

Order is a prime power. Let \(F\) be a finite field. Since every field is an integral domain, by Characteristic of an Integral Domain, \(F\) has characteristic \(p\) for some prime \(p\) (the characteristic cannot be \(0\) since \(F\) is finite). Thus \(p \cdot x = 0\) for every \(x \in F\). Suppose, for contradiction, that some prime \(q \neq p\) divides \(|F|\). Viewing \(F\) as an additive Abelian group, Cauchy's theorem for Abelian groups produces an element of additive order \(q\). But every element has additive order dividing \(p\), a contradiction. Hence \(|F| = p^n\) for some positive integer \(n\).

Existence of \(GF(p^n)\). Let \(g(x) = x^{p^n} - x \in \mathbb{Z}_p[x]\) and let \(E\) be a splitting field of \(g(x)\) over \(\mathbb{Z}_p\). Since \(g\) splits in \(E\), it has \(p^n\) zeros in \(E\) counted with multiplicity. The formal derivative \(g'(x) = p^n \cdot x^{p^n - 1} - 1\) reduces to \(-1\) in \(\mathbb{Z}_p[x]\), since \(p^n \cdot 1 = 0\) in \(\mathbb{Z}_p\). If two of the \(p^n\) linear factors of \(g\) in \(E[x]\) coincided, say both equal to \(x - \alpha\), then \((x - \alpha)^2\) would divide \(g(x)\) in \(E[x]\), and A Repeated Zero Is a Zero of the Derivative would give \(g'(\alpha) = 0\), whereas \(g'(\alpha) = -1 \neq 0\). Hence \(g\) has \(p^n\) distinct zeros in \(E\).

Now, the zero set of \(g\) is closed under field operations. For any zeros \(a, b \in E\), the Frobenius Identity gives \((a \pm b)^{p^n} = a^{p^n} \pm b^{p^n} = a \pm b\). Multiplicativity \((ab)^{p^n} = ab\) and closure under inverses \((a^{-1})^{p^n} = a^{-1}\) follow directly from \(a^{p^n} = a\). Hence the zero set of \(g\) is itself a subfield of \(E\). Since it contains \(\mathbb{Z}_p\) and all the roots of \(g\), the minimality of the splitting field forces it to equal \(E\). Therefore \(|E| = p^n\).

Uniqueness up to isomorphism. Now let \(K\) be any field of order \(p^n\). The additive subgroup \(\{k \cdot 1 : k \in \mathbb{Z}\}\) generated by \(1\) has \(p\) elements (the first part gives \(K\) characteristic \(p\)), is closed under multiplication since \((k \cdot 1)(l \cdot 1) = kl \cdot 1\), and \(k \mapsto k \cdot 1\) identifies it with \(\mathbb{Z}_p\). So \(K\) contains a copy of \(\mathbb{Z}_p\). By a purely group-theoretic argument, every element of \(K\) is a zero of \(g(x) = x^{p^n} - x\). Indeed, the nonzero elements of \(K\) form a multiplicative group \(K^*\) of order \(p^n - 1\), so the Corollaries of Lagrange's Theorem give \(a^{p^n - 1} = 1\), hence \(a^{p^n} = a\), for every \(a \in K^*\), and \(0\) is trivially a zero. Hence \(K\) consists of exactly the \(p^n\) roots of \(g\), so \(K\) is a splitting field of \(g\) over \(\mathbb{Z}_p\). By the Uniqueness of Splitting Fields, any two finite fields of order \(p^n\) are isomorphic.

Proof:

Since \(GF(p^n)\) is a finite field of order \(p^n\), the proof of the Classification of Finite Fields shows that it has characteristic \(p\), so every nonzero element has additive order \(p\). Hence the additive group of \(GF(p^n)\) is an elementary Abelian \(p\)-group of order \(p^n\). By the Fundamental Theorem of Finite Abelian Groups, it decomposes as \(\bigoplus_i \mathbb{Z}_{p^{a_i}}\) with \(\sum_i a_i = n\). The constraint that every element has order dividing \(p\) forces each \(a_i = 1\), giving \(n\) summands isomorphic to \(\mathbb{Z}_p\).

To see that the multiplicative group \(GF(p^n)^*\) of nonzero elements of \(GF(p^n)\) is cyclic, we first note that since \(GF(p^n)\) is a field, multiplication is commutative, so \(GF(p^n)^*\) is a finite Abelian group. By the Fundamental Theorem of Finite Abelian Groups, \(GF(p^n)^*\) is isomorphic to a direct product of the form: \[ \mathbb{Z}_{n_1} \oplus \mathbb{Z}_{n_2} \oplus \ldots \oplus \mathbb{Z}_{n_m}. \] If the orders of these components are pairwise relatively prime, then it follows from Criterion for \(G_1 \times G_2 \times \cdots \times G_n\) to be Cyclic that \(GF(p^n)^*\) is cyclic.

Assume for the sake of contradiction that these orders are not pairwise relatively prime. Then there exists an integer \(d \gt 1\) that divides the orders of at least two of the components. From the Fundamental Theorem of Cyclic Groups, we know that each of these components has a unique subgroup of order \(d\).

Consequently, \(GF(p^n)^*\) contains at least two distinct subgroups, \(H\) and \(K\), both of order \(d\). Since \(H \neq K\), the union \(H \cup K\) contains strictly more than \(d\) elements. However, every element in both \(H\) and \(K\) satisfies the equation \(x^d = 1\), meaning they are all roots of the polynomial \(x^d - 1\).

The polynomial \(x^d - 1\) thus has strictly more than \(d\) roots although its degree is \(d\). This contradicts the theorem that a polynomial of degree \(d\) over a field has at most \(d\) zeros. Thus, the components must be pairwise relatively prime, and \(GF(p^n)^*\) is cyclic.

Being cyclic of order \(p^n - 1\), the multiplicative group \(GF(p^n)^*\) is isomorphic to \(\mathbb{Z}_{p^n - 1}\) by the classification of finite cyclic groups by order. Both claims of the theorem are now established.

Proof:

Since \(a\) generates \(GF(p^n)^*\), every nonzero element of \(GF(p^n)\) is a power of \(a\), and thus \(GF(p)(a) \supseteq GF(p^n)\). The reverse inclusion is immediate from \(a \in GF(p^n)\). Hence \(GF(p)(a) = GF(p^n)\), and \[ [GF(p)(a) : GF(p)] = [GF(p^n) : GF(p)] = n \] by the Degree of \(GF(p^n)\). In particular \(GF(p)(a)\) has finite \(GF(p)\)-dimension, so \(a\) is algebraic over \(GF(p)\) by Finite Implies Algebraic. Let \(m(x) \in GF(p)[x]\) be its minimal polynomial, the monic irreducible polynomial of least degree with \(m(a) = 0\) supplied by the Characterization of Extensions. By the structure theorem for \(F(a)\) applied to \(m(x)\), the dimension \([GF(p)(a) : GF(p)]\) equals \(\deg m(x)\). Combined with the equality above, this gives \(\deg m(x) = n\), so \(a\) is algebraic over \(GF(p)\) of degree \(n\).

Proof:

The case \(d = 1\). If \(d = 1\), then \(a \in \mathbb{Z}_p\) and \(a\) is the only zero of \(f(x)\). The listed sequence is just \(\{a\}\) and the claim is immediate.

The case \(d \geq 2\): Each \(a^{p^i}\) is a zero of \(f(x)\). Write \(f(x) = c_d x^d + c_{d-1} x^{d-1} + \cdots + c_1 x + c_0\) with \(c_j \in \mathbb{Z}_p\). The nonzero elements of the field \(\mathbb{Z}_p\) form a group \(\mathbb{Z}_p^*\) of order \(p - 1\) under multiplication, and the Corollaries of Lagrange's Theorem yield \(c^{p-1} = 1\) for every \(c \in \mathbb{Z}_p^*\). Multiplying by \(c\) gives \(c^p = c\), and this also holds (trivially) at \(c = 0\). By induction on \(i\), \(c^{p^i} = c\) for every \(c \in \mathbb{Z}_p\) and every \(i \geq 0\).

Now apply the Frobenius map \(\phi: x \mapsto x^p\) iterated \(i\) times to the equation \(f(a) = 0\). The Frobenius Identity makes \(\phi\) (and hence \(\phi^i\)) a ring homomorphism on \(E\), so \[ \begin{align*} 0 &= \phi^i\bigl(f(a)\bigr) \\\\ &= \sum_{j=0}^d c_j^{p^i} \bigl(a^{p^i}\bigr)^j \\\\ &= \sum_{j=0}^d c_j \bigl(a^{p^i}\bigr)^j \\\\ &= f\bigl(a^{p^i}\bigr), \end{align*} \] where the third equality uses \(c_j^{p^i} = c_j\) for \(c_j \in \mathbb{Z}_p\). Thus \(a^{p^i}\) is a zero of \(f(x)\) for each \(i = 0, 1, \ldots, d-1\).

The zeros are distinct. Suppose, for contradiction, that \(a^{p^m} = a^{p^n}\) for some \(0 \leq n \lt m \leq d - 1\), and set \(j = m - n\) (so \(1 \leq j \leq d - 1\)). Then \[ \begin{align*} 0 &= a^{p^m} - a^{p^n} \\\\ &= \bigl(a^{p^j}\bigr)^{p^n} - a^{p^n} \\\\ &= \bigl(a^{p^j} - a\bigr)^{p^n}, \end{align*} \] where the last equality is the Frobenius Identity \((u - v)^{p^n} = u^{p^n} - v^{p^n}\) when \(n \geq 1\), and is trivial when \(n = 0\). Since \(E\) is a field (no zero-divisors), \(a^{p^j} = a\).

Consider \(K = \{x \in \mathbb{Z}_p(a) \mid x^{p^j} - x = 0\}\). The set \(K\) is closed under field operations by the Frobenius Identity, exactly as in the proof of the Classification of Finite Fields, so \(K\) is a subfield of \(\mathbb{Z}_p(a)\). Moreover \(K\) consists of roots of the polynomial \(x^{p^j} - x\), and a polynomial of degree \(p^j\) has at most \(p^j\) zeros. Hence \(|K| \leq p^j\). On the other hand \(K\) contains \(\mathbb{Z}_p\) (since \(c^p = c\) implies \(c^{p^j} = c\) for \(c \in \mathbb{Z}_p\)) and contains \(a\) (since \(a^{p^j} = a\)), so by minimality \(K \supseteq \mathbb{Z}_p(a)\).

Now since \(f(x)\) is irreducible over \(\mathbb{Z}_p\) with zero \(a\), the structure theorem for \(F(a)\) gives \([\mathbb{Z}_p(a) : \mathbb{Z}_p] = d\), so \(|\mathbb{Z}_p(a)| = p^d\) and \(|K| \geq p^d\). Therefore \(p^j \geq p^d\), that is, \(j \geq d\), which contradicts \(j \leq d - 1\). The zeros \(a, a^p, \ldots, a^{p^{d-1}}\) are therefore distinct.

Since \(f(x)\) has degree \(d\) and we have produced \(d\) distinct zeros, these are all of its zeros.

Proof:

Let \(d = \deg f(x)\). By the Zeros of an Irreducible over \(\mathbb{Z}_p\), the zeros of \(f(x)\) are \(a, a^p, a^{p^2}, \ldots, a^{p^{d-1}}\), all distinct. Since \(a \in \mathbb{Z}_p(a)\) and \(\mathbb{Z}_p(a)\) is closed under multiplication, every \(a^{p^i}\) lies in \(\mathbb{Z}_p(a)\). With \(d\) distinct roots in hand, repeated use of the Factor Theorem and a comparison of degrees show that \(f(x)\) factors completely over \(\mathbb{Z}_p(a)\) as \[ f(x) = c_d (x - a)(x - a^p) \cdots \bigl(x - a^{p^{d-1}}\bigr), \] where \(c_d \in \mathbb{Z}_p\) is the leading coefficient. That is, \(f(x)\) splits in \(\mathbb{Z}_p(a)\).

For minimality, the field generated over \(\mathbb{Z}_p\) by all the roots is \(\mathbb{Z}_p(a, a^p, \ldots, a^{p^{d-1}}) = \mathbb{Z}_p(a)\). Indeed, each \(a^{p^i}\) already lies in \(\mathbb{Z}_p(a)\), and \(a\) is itself one of the listed roots. By the Definition of Splitting Field, \(\mathbb{Z}_p(a)\) is the splitting field of \(f(x)\) over \(\mathbb{Z}_p\).

Proof:

The candidate subfield. Suppose \(d \mid n\). Then \(p^d - 1\) divides \(p^n - 1\). Writing \(n = dq\), the geometric-series factorization \[ \begin{align*} p^n - 1 &= (p^d)^q - 1 \\\\ &= (p^d - 1)\bigl((p^d)^{q-1} + (p^d)^{q-2} + \cdots + 1\bigr) \end{align*} \] exhibits the divisibility. Consider the set \[ K = \{x \in GF(p^n) \mid x^{p^d} = x\}, \] which is exactly the zero set of the polynomial \(x^{p^d} - x\) inside \(GF(p^n)\). The Frobenius Identity shows that \(K\) is closed under field operations (the computation is the one already used for the Classification of Finite Fields), so \(K\) is a subfield of \(GF(p^n)\).

\(|K| = p^d\). The polynomial \(x^{p^d} - x\) has degree \(p^d\), so a polynomial of degree \(p^d\) has at most \(p^d\) zeros in \(GF(p^n)\). Hence \(|K| \leq p^d\).

For the reverse inequality, by the Structure of Finite Fields the multiplicative group \(GF(p^n)^*\) is cyclic of order \(p^n - 1\), so by the Fundamental Theorem of Cyclic Groups it contains a (unique) subgroup \(H\) of order \(p^d - 1\). Every \(x \in H\) satisfies \(x^{p^d - 1} = 1\) (since \(H\) is cyclic of order \(p^d - 1\), every element's order divides \(p^d - 1\)), hence \(x^{p^d} = x\), so \(H \subseteq K\). Combined with \(0 \in K\), we get \(|K| \geq |H| + 1 = p^d\). Therefore \(|K| = p^d\), and \(K\) is a subfield of \(GF(p^n)\) of order \(p^d\).

Uniqueness. Let \(K'\) be any subfield of \(GF(p^n)\) of order \(p^d\). Every nonzero \(x \in K'\) lies in \((K')^*\) of order \(p^d - 1\), so \(x^{p^d - 1} = 1\) by the Corollaries of Lagrange's Theorem, giving \(x^{p^d} = x\). The same holds at \(x = 0\). Hence \(K' \subseteq K\). Since \(|K'| = |K| = p^d\), we conclude \(K' = K\). The subfield of order \(p^d\) is unique.

Only divisors give subfields. Conversely, let \(K\) be any subfield of \(GF(p^n)\). Identifying the prime subfield of \(GF(p^n)\) with \(\mathbb{Z}_p\), we have \(\mathbb{Z}_p \subseteq K \subseteq GF(p^n)\). Both extensions are finite, since \(GF(p^n)\) is a finite set, so the Tower Rule gives \[ [GF(p^n) : \mathbb{Z}_p] = [GF(p^n) : K] \cdot [K : \mathbb{Z}_p]. \] Set \(d = [K : \mathbb{Z}_p]\). Then \(K\) is a \(\mathbb{Z}_p\)-vector space of dimension \(d\), so \(|K| = p^d\). The above equation reads \(n = [GF(p^n) : K] \cdot d\), so \(d \mid n\). Therefore the order of any subfield of \(GF(p^n)\) is \(p^d\) for some divisor \(d\) of \(n\).

Proof:

Let \(g(x)\) be an irreducible factor of \(x^{p^n} - x\) over \(\mathbb{Z}_p\), and set \(d = \deg g(x)\). Let \(E\) be a splitting field of \(x^{p^n} - x\) over \(\mathbb{Z}_p\). The proof of the Classification of Finite Fields shows that \(E\) consists exactly of the \(p^n\) distinct zeros of \(x^{p^n} - x\), so \(E = GF(p^n)\) and \(x^{p^n} - x\) is a product of distinct linear factors in \(E[x]\). Since \(g(x)\) divides \(x^{p^n} - x\), unique factorization in \(E[x]\) (\(F[x]\) is a UFD) shows that \(g(x)\) is, up to a unit, a product of some of these linear factors. Hence \(g(x)\) has a zero \(a \in GF(p^n)\), and \(\mathbb{Z}_p(a) \subseteq GF(p^n)\).

By the Splitting Field of an Irreducible Polynomial Over \(\mathbb{Z}_p\), \(\mathbb{Z}_p(a)\) is the splitting field of \(g(x)\) over \(\mathbb{Z}_p\). Because \(g(x)\) is irreducible over \(\mathbb{Z}_p\) with zero \(a\), the structure theorem for \(F(a)\) gives \([\mathbb{Z}_p(a) : \mathbb{Z}_p] = d\). Hence \(|\mathbb{Z}_p(a)| = p^d\), and \(\mathbb{Z}_p(a)\) is a subfield of \(GF(p^n)\) of order \(p^d\). By the Subfields of a Finite Field, \(d \mid n\).