Finite fields

Finite fields are one of the few examples of an algebraic structure where one can classify everything completely.

We saw earlier how to make a finite field.

Theorem

Let p be a prime and f(x) an irreducible polynomial of degree k in Z_p[x]. Then Z_p[x]/ < f(x) > is a field with p^k elements.

Proof
Note that a polynomial is irreducible if it cannot be written as a product of polynomials of lower degree.
As in the last section we can choose as coset representatives polynomials of the form a₀ + a₁x + a₂x² + ... + a_k-1x^k-1 and so we get a ring of order p^k.
As in Z_n we use the Euclidean algorithm to find the inverse of an element.
Let g(x) be a coset representative of an element of the field. Since f (x) is irreducible it is not divisible by any lower degree polynomial and so the gcd(g(x), f (x)) = 1. Then by the Euclidean algorithm 1 = a(x)g(x) + b(x)f (x) for some polynomials a(x), b(x). Then a(x) is a coset representative for the inverse of g(x).

Here are some results I don't have time to prove.

Important fact

For every prime p and positive integer k there is an irreducible polynomial of degree k in Z_p[x]. Hence there is a field of order p^k.

Remarks

1. In fact there are lots of such polynomials. For example, take p = 3. Then with k = 2 there are 3 monic (leading coefficient 1) irreducible polynomials out of 9; with k = 3 there are 8 out of 27; with k = 5 there are 48 out of 243; ...

2. It is easy to tell if a quadratic or cubic is irreducible since if it were not it would have a linear factor and so the polynomial would have a root. That is easy to check! However, higher degree polynomials are harder. For example, the polynomial x⁴ + 1 ∈ Z₂[x] has no root, but is reducible since it is (x² + 1)².

Any two fields of order p^k are isomorphic as rings.

Example

We saw in the last section that the map defined by 1 ↦ 1 and x ↦ y + 1 is a ring isomorphism from Z₃[x]/ < x² +1 > to Z₃[y]/ < y²+ 2y +2 > and this is the unique field of order 9.

Following Exercises 2 Qu 6 we look at the the subring of a finite field generated by 1 and deduce that 1 has a prime number p for its additive order and that hence every non-zero element has this same order.

Definitions

This prime number is called the characteristic of the field.

The subfield generated by 1 is called the prime subfield and is isomorphic to Z_p .

Remark

If the element 1 does not have a finite order (in which case the field is not finite) we say the characteristic of the field is 0. In a field with characteristic 0 the element 1 generates a subfield isomorphic to the rational numbers Q.

Theorem

Any field is a vector space over any subfield.

Proof
it is easy to verify the axioms.

If E is a subfield of F then we can choose a basis for F over E. The number of elements in the basis is called the dimension of F over E and is written [E: F].

In particular, if F is finite with |F| = p^k it is a field of dimension k over its prime subfield.

Now let r be any element not in the prime subfield of the field F of size p^k. Then consider the elements 1, r, r², r³, ... Eventually this list will stop producing linearly independent vectors and then one has a set {1, r, r² , ... , r^m-1 } of independent vectors and a polynomial f(r) = a₀ + a₁r + a₂r² + ... + a_mr^m = 0 with coefficients in the prime field Z_p .
The subspace spanned by this set is a subfield and has size p^m.
This polynomial f is called the minimal polynomial of the element r and since the field is a vector space over this subfield we must have m divides k.

A important result about finite fields is:

The cyclic group theorem

The multiplicative group of a finite field is cyclic.

Proof
In Exercises 4 Qu 6 you should have already noticed that the multiplicative group U_n of Z_n is cyclic if n is prime.

The main result we need to prove this in general is:

Lemma
A polynomial of degree k with coefficients in a field can have at most k roots.

Proof of lemma
If a polynomial f(x) over a field has a root α then divide f(x) by x - α to get f(x) = (x - α)q(x) + r. Since f(α) = 0 it follows that r = 0 and the polynomial is divisible by x - α. Hence the polynomial has a linear factor for each root and so cannot have more that deg(f) roots.

Before we prove our theorem we look at a particular case.
Consider the multiplicative group of the field with 9 elements. This abelian group has order 8 and so is one of C₈ , C₄ × C₂ or C₂ × C₂ × C₂ . If it were not C₈ then any element r would satisfy r⁴ = 1. But then the polynomial x⁴ - 1 would have too many roots.

The general proof is similar. The multiplicative group of a field with order p^k has order p^k - 1 and suppose we have some prime q dividing this. Then the elements of the multiplicative group whose order is a power of q form a subgroup of order q^s (say). If this group is not cyclic then every element r of this subgroup satisfies r^s-1 = 1 and then the polynomial x^s-1 - 1 would have too many roots.
So the multiplicative group is a direct product of cyclic groups corresponding to various primes and hence is cyclic.

In particular we have now proved the result mentioned above:

If n is prime, the group of units of Z_n is cyclic.

Remark

The fact that the multiplicative group of GF(p^k) is cyclic makes it very conveneient for calculation. We can choose a particular multiplicative generator z (say) and then all the other elements are powers of this. So multiplication is easy. To calculate the sum of two elements z^m and zⁿ (say) observe that z^m + zⁿ = z^m(1 + z^n-m) and so we need only store a table which writes 1 + z^r as a power of z.