Rings and Fields

 Previous page (Factor rings and the isomorphism theorems) Contents Next page (Contents)

## 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 Zp[x]. Then Zp[x]/ < f(x) > is a field with pk 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 a0 + a1x + a2x2 + ... + ak-1xk-1 and so we get a ring of order pk.
As in Zn 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 Zp[x]. Hence there is a field of order pk.

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 x4 + 1 ∈ Z2[x] has no root, but is reducible since it is (x2 + 1)2.

Very important fact

Any two fields of order pk are isomorphic as rings.

Example

We saw in the last section that the map defined by 1 ↦ 1 and xy + 1 is a ring isomorphism from Z3[x]/ < x2 +1 > to Z3[y]/ < y2+ 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 Zp .

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| = pk 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 pk. Then consider the elements 1, r, r2, r3, ... Eventually this list will stop producing linearly independent vectors and then one has a set {1, r, r2 , ... , rm-1 } of independent vectors and a polynomial f(r) = a0 + a1r + a2r2 + ... + amrm = 0 with coefficients in the prime field Zp .
The subspace spanned by this set is a subfield and has size pm.
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 Un of Zn 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 C8 , C4 × C2 or C2 × C2 × C2 . If it were not C8 then any element r would satisfy r4 = 1. But then the polynomial x4 - 1 would have too many roots.

The general proof is similar. The multiplicative group of a field with order pk has order pk - 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 qs (say). If this group is not cyclic then every element r of this subgroup satisfies rs-1 = 1 and then the polynomial xs-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 Zn is cyclic.

Remark

The fact that the multiplicative group of GF(pk) 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 zm and zn (say) observe that zm + zn = zm(1 + zn-m) and so we need only store a table which writes 1 + zr as a power of z.

 Previous page (Factor rings and the isomorphism theorems) Contents Next page (Contents)

JOC/EFR 2004