Finite Fields

In this section we consider finite fields. In particular we show that if K is a finite field then |K| = pⁿ for some prime p and natural number n > 0. Further we show that if K₁, K₂ are finite fields with |K₁| = |K₂| then K₁ ≌ K₂. Hence there is a unique finite field for each possible order. Notice that if K is a finite field then by necessity char K = p ≠ 0 (see Remark Remark 4.15.4).

8.3.1 Definition. Let F a field and let f(x) = a_nxⁿ + a_{n − 1}x^{n − 1} + ... + a₁x + a₀ a polynomial in F[x]. We define the derivative of f(x), and we indicate it by f'(x), the polynomial in F[x]:

which is a polynomial of degree at most n − 1. It is to verify that the ordinary rules of calculus hold:

8.3.2 Proposition. A polynomial f(x) ∈ F[x] has a multiple root (in some extension field) if and only if f(x) and f'(x) have a common non-trivial factor (i.e. with degree greater than one).

Proof. First notice that it is immaterial to specify over which field f(x) and f'(x) have a common non-trivial factor; If they have a common non-trivial factor in a field K ⊆ F then they have a common non-trivial factor in F as well, indeed from the relation

which says that f(x) and f'(x) are coprime in F would be a relation true in K as well, then the two polynomials would be coprime in K as well. Let α an arbitrary multiple root of f(x), that is

Then

from which it results that α is a root of f'(x) as well.
Conversely, suppose that f(x) and f'(x) have a common non-trivial factor. By contradiction, suppose first that f(x) has no multiple roots, that is let

with α_i, all distinct among each other. Then, applying the product rule (fg)' = f'g + fg' to calculate the derivative

notice that the product rule extends to (fgh)' = f'gh + fg'h + fgh'; for example if f(x) = (x − a₁)(x − a₂)(x − a₃), then f'(x) = (x − a₂)(x − a₃) + (x−a₁)(x − a₃) + (x − a₁)(x − a₂), and f'(a₁) = (a₁ − a₂)(a₁ − a₃) ≠ 0.
From which it results that f'(α_i) ≠ 0 for every i = 1, ..., n and this contradicts the assumption that f(x) and f'(x) have a common non-trivial factor.  □

Indeed, In the example above, imagine α₁ = α₂ is a double root. Notice that (x − α₁) divides both f and f'.

8.3.3 Definition An irreducible polynomial p(x) ∈ F[x] is separable if it has no multiple roots in any extension of F, otherwise it is called inseparable over F.  □

8.3.4 Example The polynomial f(x) = x − 5 ∈ ℚ[x] is irreducible over ℚ, and has all distinct roots. ■

8.3.5 Example Let K = ℤ₃(t) is the field of rational functions in the indeterminate t, with coefficients in ℤ₃. The polynomial

is inseparable. Let α one of its roots (in its splitting field). Then it results α³ = t, from which

so if β is another root of f(x), then

It remains to prove that f(x) = x³ − t is irreducible over ℤ₃(t). If it were reducible, being a polynomial of 3rd degree it would possess a root. Elements of ℤ₃(t) are of the form

Suppose by contradiction that α(t) = A(t)/B(t) is a root of x³ − t. Then α³ − t = 0 i.e A(t)³ / B(t)³ − t = 0, so so A(t)³ = t B(t)³, which is clearly impossible. Similarly to how you might show √2 = a/b is impossible. certainly, a is not in ℤ₃(t) just like how √2 is not in ℚ but we can extend it to get ℤ₃(t)[a], as we did ℚ[√2] ■

The following proposition indicates in which cases an irreducible polynomial has no multiples roots: irreducibility + char 0 of F ⇒ separability. We give first a sketch of the proof with an example. f(x) = x² + x + 1 is irreducible over ℚ. We have f'(x) = 2x + 1. Suppose f(x) and f'(x) had a common factor. Since f'(x) has degree 1, then this common factor cannot have degree > 1. But f(x) is irreducible, so any factor of f(x) of degree < 2 must be a constant. Therefore, the only common factors of f(x) = x² + x + 1 and f'(x) = 2x + 1 are the (nonzero) constants and by Proposition 8.3.2, f(x) must be separable.

8.3.6 Proposition Let f(x) ∈ F[x] an irreducible polynomial. Then, if F has characteristic zero, f(x) is always separable. If F has characteristic p, f(x) is inseparable if and only if f(x) = g(x^p), i.e. f is a polynomial in the variable x^p:

Proof. We know that a polynomial f(x) is inseparable if and only if f(x) and f'(x) have a common factor of degree ≥ 1. But, being in this case f(x) irreducible, and since f'(x) has degree less than that of f(x), it follows that an irreducible polynomial is inseparable if and only if f'(x) = 0, that is

(the derivative of a_i xⁱ is i a_i x^{i − 1}). Now, if the characteristic is zero, these relations imply that a_i = 0 for every i = 1, ..., n, that is f(x) is a constant a₀, hence, without roots. If the characteristic if p, relations 8.3.1 imply that the coefficients a_i for which i ≡ 0 (mod p) is not verified must be zero. Thus f(x) is a polynomial composed by powers of x^p. Conversely every such a polynomial is inseparable since its derivative is zero.  □

8.3.7 Proposition Every finite field F has pⁿ elements, with p prime.

Proof. We've already proved the theorem in exercise 11; we repeat it for the sake of completeness. Every finite field F has finite characteristic p, and hence extension of the field ℤ_p (see Theorem 4.15.5). It results thus a vector space of dimension n over ℤ_p, for some positive integer n, then K has pⁿ elements .  □

8.3.7 Lemma. Every element a of a finite field with pⁿ elements satisfies the relation

Proof. If a is 0 the relation is true. Consider then the elements a ≠ 0 in F. These elements constitute a group (F\{0} is always a group under *). From Corollary 7.9.5 of Lagrange's theorem:

which multiplied by both sides by a, leads to the relation sought.  □

8.3.8 Lemma. A field F with pⁿ elements is the splitting field of the polynomial

Proof. By the previous lemma the pⁿ elements of the field F satisfy the polynomial x^pn − x. Such polynomial can't have more roots since the degree is pⁿ. Thus the polynomial x^pn − x splits in F. It cannot split in a smaller field since some roots would not be included. Thus F is the splitting field for x^pn − x.  □

8.3.9 Lemma. Two fields with pⁿ elements are isomorphic.

Proof. They are both the splitting fields of the same polynomial x^pn − x, thus they are isomorphic by the uniqueness of the splitting field of a polynomial.  □

8.3.10 Theorem. Given a prime p and an integer n there exists a field with pⁿ elements.

Proof. Starting from the integer n and prime number p, we construct the polynomial

In the splitting field L, of the polynomial, consider the subset

The cardinality of L is equal to the distinct roots of x^pn − x; but these roots are all distinct (calculate the derivative: since pⁿ = 0 then f'(x) = −1, so it has no nontrivial common factors with f, see Proposition 8.3.2). Thus |K| = pⁿ. By showing that this subset is a field, we would have found the desired field coincident with L. It suffices to show that for every a,b ∈ K, a ± b, ab and ab⁻¹ are in K as well. Indeed the following relations modulo p are satisfied

8.3.11 Theorem. The multiplicative group of a finite field is cyclic.

Proof 1. Let F a finite field and consider its multiplicative group F* = F \ {0}. Being a finite abelian group, (using the same notation employed in the theorem on the structure of finite abelian groups):

where the q_i are primes that appear in the factorization of the order |K*| = pⁿ − 1, and each Σ_qi is the product of cyclic groups. To prove that K* is cyclic it suffices to show that each Σ_qi is cyclic, that is, possesses an element with period its order. For the sake of simplicity, let's drop the _i here, we don't need it. We have

with α₁ + α₂ + ... α_r = α, and |Σ_q| = q_i^α. By way of contradiction suppose that the maximum order of the elements of Σ_q is q^α₁ < q^α. Then for every element s of Σ_qi we have that s^qα₁ = 1. But this is a contradiction since the polynomial x^qα₁ − 1 has more roots (which are q^α) than its degree.  □

Proof 2. Let F = n. Then F* is a finite abelian group n − 1 elements. Let q be the lcm of the orders of all elements of F*. Then a^m = e for all a ∈ F*. Hence every element in F* is a root of the polynomial x^m − 1. But a polynomial of degree m can have at most m roots. Hence n − 1 ≤ m. We already showed in Lemma 7.4.3 that, there exists an element c in F* of order m. Hence m divides n − 1, and this proves q = n − 1. F* is a cyclic group generated by c.  □

8.3.12 Proposition. Every finite field F with characteristic p has an automorphism σ, known as Frobenius automorphism, such that σ(a) = a^p for every a ∈ F.

Proof. σ is bijective and preserves group operations.  □

Exercises

1. Check whether fields of the following order exists, and in case construct them: 16, 24, 167, 2867.

2. Let K a field, with |K| = pⁿ. Prove that there exists a polynomial p(x) ∈ ℤ_p[x] with degree n such that K ≃ ℤ_p[x]/(p(x)).

3. Construct a field having 25 elements.

4. Let K a field with |K| = pⁿ elements. If F is a subfield of K, prove that |F| = p^m, where m divides n. Prove the converse as well: for every divisor m of n there exists a single subfield F of K with |F| = pⁿ.

5. Find all subfields of fields, with 64, 125 and 3125 elements.

Solution

1. • 16 = 2⁴, so there exits a field with 16 as order. A field can be constructed as ℤ₂/(p(x), with p(x) is an irreducible polynomial od degree 4 over ℤ₂. For example p(x) = x⁴ + x + 1 is irreducible: since x² + 1 has a zero of 1 in ℤ₂, you know that x² + 1 cannot be a factor, so you are left with (x² + x + 1)(x² + x + 1) = x⁴ + x² + 1. The elements of the field are all of the form q(x) + ⟨x⁴ + x + 1⟩ where q(x) is a degree 3 or less polynomial, and there are 2⁴ polynomials of the form ax³ + bx² + cx + d in ℤ₂. ■

   • 24 cannot be expressed in terms of any power, hence there's no field with cardinality 24. ■

   • It suffices to show that it's not divisible by 2,3,5,7,12. Since 167 is prime there exists a field which 167 elements which is ℤ₁₆₇. ■

   • Use Fermat's method to find a factorization 2867 = 47 ⋅ 61, so it's not expressible as p^k. ■

2. We know, from 8.3.11 that the multiplicative group of a finite field is cyclic. Let a a generator of the group K\{0}, then a^{pn −1} = 1. We shall prove that a is algebraic with degree n. Consider the polynomial f(x) = x^pn − x ∈ ℤ_p[x]; being a polynomial with coefficients in a field, f(x) is the product of irreducible polynomials (see Unique factorization theorem), and since a is a root of f(x), it must be root of some irreducible polynomial, say, g(x). Then ℤ_p(a) ≃ ℤ_p[x]/g(x), and since ℤ_p(a) = K has pⁿ elements, by Theorem 8.12.2 (d), it means that g(x) has degree n.  ■

3. Such a field exists since 5² = 25. Such a field can be thought as the splitting field over of x²⁵ − x (as in Theorem 8.3.10). Or using the result "For a prime p and a monic irreducible polynomial p(x) in F_p[x] of degree n, then the ring (F_p[x]/⟨p(x)⟩) is a field of order pⁿ", by taking e.g. x² + 3 which is irreducible in ℤ₅, as does x² + 2. Those are the only two that work in ℤ₅.

   ℤ₅[x]/(x² + 3), Then ℤ₅[x]/(x² + 3) = {a+bx+(x²+3), a,b ∈ ℤ₅}. The elements of K are thus

   0,1,2,3,4,
   x,2x,3x,4x,
   1+x,1+2x,1+3x,1+4x,
   2 +x, 2+2x, 2+3x, 2+4x,
   3+x, 3+2x, 3+3x, 3+4x,
   4+x, 4+2x, 4+3x,3+4x

   It's not hard to find that 2 + x is the generator of the multiplicative group K*.

4. It results K ⊃ F ⊃ ℤ_p. Now, n = [K : ℤ_p] = [K: F][F : ℤ_p], thus [F : ℤ_p] = m |n, from which |F| = p^m with m | n. Conversely we shall prove that for every divisor m of n there exists a unique subfield F of K with p^m elements. If such a field exists, every element of F satisfies the polynomial f(x) = x^pm − x and f(x) has at most p^m roots in K: thus if such F exists is necessarily unique. On the other hand the set F of all roots of f(x) is a subfield with p^m elements and is contained in K: indeed every root of f(x) in the subfield contained within the splitting field L, is also root of x^pn − x = 0: dividing both sides of x^pm = x, by x we have x^pm−1 = 1; By raising both sides to (p^{n − 1})/(p^{m − 1}) we have x^pn−1 = 1; since raising both sides of an equation to (pⁿ⁻¹)/(p^m−1) makes sense only if p^{m − 1}| p^{n − 1} is an integer we make sure it really is by Lemma 8.6.1. Since, K is the splitting field for x^pn − x, all roots of f(x) are in K, hence F ⊆ K.  ■

5. A field of order 64 = 2⁶ has three subfields: one of order 2 (that is ℤ₂), one with order 2² (i.e. ℤ₂[x]/(x²+x+1)), 2³, and one of order 2⁶, i.e. the entire field itself.
   A field of order 125 = 5³ contains a subfield of order 5 (i.e. ℤ₅), and the entire field.
   A field of order 3125 = 5⁵ has subfields of order 5 (i.e. ℤ₂), and one of order 3125 i.e. the field itself.  ■