Finite Fields

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]\), so \(\gcd(g, g') = 1\) and \(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 binomial theorem in characteristic \(p\) gives \((a + b)^{p^n} = a^{p^n} + b^{p^n} = a + 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 gives that it equals \(E\). Therefore \(|E| = p^n\).

Uniqueness up to isomorphism. Conversely, let \(K\) be any field of order \(p^n\). The prime subfield generated by \(1\) is isomorphic to \(\mathbb{Z}_p\). Since the multiplicative group \(K^*\) has order \(p^n - 1\), Lagrange's theorem gives \(a^{p^n - 1} = 1\) for every \(a \in K^*\), so every element of \(K\) (including \(0\)) is a zero of \(g(x) = x^{p^n} - x\). Hence \(K\) consists of exactly the \(p^n\) roots of \(g\), so \(K\) is a splitting field of \(g\) over \(\mathbb{Z}_p\). Splitting fields of a given polynomial over a given field are unique up to isomorphism, so 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 they are not pairwise relatively prime. Then there exists an integer \(d > 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\).

This means that the overall group \(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\).

This yields strictly more than \(d\) roots for a polynomial of degree \(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.

We have established both claims of the theorem. The additive group is isomorphic to the direct product of \(n\) copies of \(\mathbb{Z}_p\), and the multiplicative group of nonzero elements is isomorphic to \(\mathbb{Z}_{p^n-1}\) and is therefore cyclic.

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)\); let \(m(x) \in GF(p)[x]\) be its minimal polynomial (which is irreducible). By the structure theorem for \(F(a)\) applied with \(p(x) = m(x)\), the dimension \([GF(p)(a) : GF(p)]\) equals \(\deg m(x)\). Combined with the equality above, \(\deg m(x) = n\); that is, \(a\) is algebraic over \(GF(p)\) of degree \(n\).

Proof:

The case \(d = 1\). If \(a \in \mathbb{Z}_p\), then \(d = 1\) 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 multiplicative group \(\mathbb{Z}_p^*\) has order \(p - 1\), so \(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 binomial theorem in characteristic \(p\) makes \(\phi\) (and hence \(\phi^i\)) a ring homomorphism on \(E\), so \[ 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), \] 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 < m \leq d - 1\), and set \(j = m - n\) (so \(1 \leq j \leq d - 1\)). Then \[ 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}, \] where the last equality is the Frobenius identity \((u - v)^{p^n} = u^{p^n} - v^{p^n}\) in characteristic \(p\). 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 same Frobenius-and-binomial computation used in the Classification of Finite Fields, so \(K\) is a subfield of \(\mathbb{Z}_p(a)\). Moreover \(K\) consists of the roots of the polynomial \(x^{p^j} - x\), so a polynomial of degree \(p^j\) has at most \(p^j\) zeros, giving \(|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\), it is (up to a constant factor) the minimal polynomial of \(a\) over \(\mathbb{Z}_p\); the structure theorem for \(F(a)\) then 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\), i.e., \(j \geq d\) — contradicting \(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, \(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)\), since on the one hand each \(a^{p^i}\) already lies in \(\mathbb{Z}_p(a)\), and on the other hand \(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 \[ p^n - 1 \;=\; (p^d)^q - 1 \;=\; (p^d - 1)\bigl((p^d)^{q-1} + (p^d)^{q-2} + \cdots + 1\bigr) \] 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 set \(K\) is closed under field operations by the same Frobenius-and-binomial computation used in 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 it 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 by Lagrange's theorem \(x^{p^d - 1} = 1\), 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)\). By the Tower Rule, \[ [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 \(a\) be a zero of \(g(x)\) in some extension field of \(\mathbb{Z}_p\). Since \(g(x) \mid x^{p^n} - x\), the element \(a\) also satisfies \(a^{p^n} = a\); hence \(a\) lies in the subfield \(\{x \mid x^{p^n} = x\} = GF(p^n)\) constructed in the proof of the Classification of Finite Fields. Then \(\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\). Since \(g(x)\) is irreducible with zero \(a\), it is (up to a constant factor) the minimal polynomial of \(a\) over \(\mathbb{Z}_p\); the structure theorem for \(F(a)\) then gives \([\mathbb{Z}_p(a) : \mathbb{Z}_p] = d\), so \(|\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, the order of any subfield of \(GF(p^n)\) is \(p^d\) for some divisor \(d\) of \(n\); therefore \(d \mid n\).