None:
Polyps:
Strongs:

Constructing Finite Fields

Constructing a finite field is not so difficult. Understanding the structures that must already be in place is the tricky part. First, we require a ring with no zero divisors. Then, as these rings are termed "Integral domains", we also note that we require a "Principal Ideal Domain", in that every ideal in our integral domain is or must be generated by a single element. Then, we require that every prime ideal in our ring is a maximal ideal (it is not included in another ideal.)

Of course, there is also the proof that every PID (Principal Ideal Domain) is a UFD (Unique Factorisation Domain) in which no two different polynomials have the same factorisation and no polynomial splits into two different factorisations of irreducible factors. This is not given here, as it is beyond the scope of the study.

In chapter 2 I posed the exercise to show that a finite field of every degree exists over every prime field Z/pZ which is isomorphic to GF(p)+ and with multiplication modulo p forms a field, and so the extension by an indeterminate "x" is an integral domain F[x]. No two polynomials in x in product give 0, there is always a term "in some power of x" and then products of scalars are in GF(p) and so there are no zero divisors. F[x] serves us well as our integral domain.

I now have to show that F[x] is a PID (from which follows that F[x] is a UFD)

Theorem 1) So, given F a field, F[x] is a PID.

Proof:

let I be any ideal of F[x]. If I= 0 then I is trivially generated by zero, and so is principal.

If p(x) is a minimal-degree polynomial in I and q(x) any element of I then I may write q(x) = p(x)s(x) + t(x) where t(x) = 0 or degree(t)<degree(p)).

NB:// if degree(p) = 1 then I = <1> = F[x] and F[x] is principal.

I is a subring, and is closed under multiplication, so because p(x) is in I, so are all p(x)s(x) with s(x) in F[x]. Similarly, I is closed under addition as a subring, so q(x) - p(x)s(x) = t(x) is in I also.

Yet p(x) was of minimal degree in I, and degree(t)<degree(p) ensures that t(x) cannot be of degree less than that of p(x). therefore t(x) = 0 and every ideal I in F[x] is a principal ideal generated by some least p(x).


Theorem 2) I state that F[x] has a maximal ideal I if and only if F[x] / I is a field.

Proof:

First I note that F[x] and F[x] / I are both commutative rings with unity as long as I is not F[x], (I is maximal). Then the set T = {nx + m : n in F[x], m in I} for some x not in I, forms an additive group. As (n1x+m1) + (n2x+m2) = (n1+n2)x + (m1+m2) which is also in T. So is 0x+0 as well as -(nx+m) = (-n)x+(-m).

Now, given I an ideal, r(nx+m) = (rn)x+rm is also in T. So, T is also an ideal. Yet x = 1.x+0 is in T as well as m = 0x+m also. So then T properly contains I. Yet I was maximal so T=F[x]. Therefore T contains the unity so there are two elements n in F[x] and m in I such that 1 = nx+m. Consequently with m in I, 1+I = nx + I = (n+I)(x+I) so x+I is a multiplicative inverse of n+I in F[x] / I.

Conversely, if F[x] / I is a field, then if J is a proper ideal of F[x] containing I (I < J < F[x]) then we may form the factor ring of (F[x] / I). Now, the morphism f: F[x] => (F[x] / I) maps the ideal J of F[x] onto the ideal f(J) which is a non-trivial ideal of F[x] / I. Hence, as F[x] / I has no non-trivial ideals being a field, I = J or J = F[x]. Hence, I is a maximal ideal.

Which was what was wanted.


Next I required to show that the minimal polynomial that generates a maximal ideal is irreducible. I will assume F[x] is an integral domain.

Theorem 3) If <p(x)> is the principal ideal I in F[x] generated by p(x), I is maximal if and only if p(x) is irreducible in F[x].

Proof:

Assuming <p(x)> is not equal to <0> and is maximal (and not equal to F[x]) then p(x) is not a unit in F. If p(x) = f(x)g(x) is a factorisation in F[x] then as we know F[x]/I is a field (an integral domain) every maximal ideal is also a prime ideal.

The definition of a prime ideal is that if any product ab is in I (a prime ideal) then a is in I or b is in I. Then the ring R/I is equal to r + I with product ab + I = (a+I)(b+I) = I if and only if a+I = I or b + I = I (There are no zero divisors.)

Then as every maximal ideal I in F[x] forms a quotient field F[x] / I which itself is an integral domain, every maximal ideal in F[x] is a prime ideal.

Then if f(x)g(x) is in <p(x)> = I then either f(x) is in I or g(x) is in I.that is, p(x) | f(x) or p(x) | g(x). But then degree(g)<degree(p) or degree(f) <degree(p) by assumption, so p(x) cannot divide either f or g. Thus, by contradiction p(x) is irreducible.

Conversely, if p(x) is irreducible and we assume (<p(x)> = I) < J < F[x] where J is any proper ideal containing I, then as every ideal in F[x] is principal, p(x) = f(x)q(x) for some f(x) where <q(x)> = J. Now, p(x) is irreducible so either f(x) or q(x) has degree 0. Then if q(x) = s for some s in F, then J = F[x] (a contradiction, so I is maximal) or f(x) = s for some unit s in F. Then, (1/s)p(x) = q(x) is in I=<p(x)> (s is in a field and has an inverse) So then I is maximal as desired.


Theorem 4) Corollary

If p(x) is irreducible in F[x] and p(x) divides f(x)g(x) then p(x) divides either f(x) or g(x) (or both).

Proof:

Given p(x) irreducible, <p(x)> = I generates a maximal ideal, which is also principal, hence f(x)g(x) is in I = <p(x)>. Then as I is maximal, f[x] / I is a field. Hence, there are no zero divisors in F[x] / I and so I is a prime ideal. Then either f(x) is in I or g(x) is in I (or both) but then p(x) | f(x) or p(x) | g(x) as desired.


It should then all come together when it is stated that we may take a root of an irreducible polynomial irr(x) and in F[x] evaluate the polynomial irr(x) at that root, along with every other polynomial in F[x]. Then every polynomial in F[x] which is a multiple of irr(x) will be evaluated to zero.

Clearly, we then operate "modulo irr(x)=0" and we construct the finite field F[x] / <irr(x)>. The conditions for this are as shown above.

First, every ideal of F[x] is principal (Theorem 1) and also maximal if and only if the principal element is irreducible. (Theorem 3) Every maximal ideal is a prime ideal, so F[x] / <irr(x)> is an integral domain, and is then a field, as it contains an inverse for every non-zero element of F[x] / <irr(x)>. (Theorem 2)

Lastly, if f(x)g(x) = 0 in (F[x] / <irr(x)>) then f(x) = 0 or g(x) = 0. And we have no zero divisors, F[x] / irr(x) is truly a field. (Theorem 4)

The "easy" part with regards to the exercise given in Chapter 2 of the book follows on the next page.


Continue To Next Page

Return To Section Start


'