Constructing a field of 4 elements

[PsychonautQQ]

This is from an example in my textbook:

"The polynomial x^2+x+1 has no root in Z mod 2, and so is irreducible. Hence the required field is:

F = Z_2[x] / <x^2 + x + 1> = {a + bt | a,b are elements of Z_2; t^2+t+1 = 0}.

Thus F = {0, 1, t, 1+t} and t^2 = t + 1."

I have two questions.
My first question is if this a exercise problem rather than an example, I would have had no idea to grab the polynomial x^2+x+1 in Z mod 2. Can somebody explain why this was apparently so obvious?

My next question is why is t^2 = t + 1? Wouldn't t^2 = -t - 1?

 

[mathman]

t+1=-t-1 (mod 2)?

 

[micromass]

Well, to obtain a field of $p^n$ elements, you want to quotient $\mathbb{F}_p[X]$ by an irreducible polynomial of degree $n$. I assume that's clear and you're really asking how to find such a polynomial. Well, that is actually a hard question and a topic of research. It has been proven (and the proof is not trivial!) that such a polynomial always exists. But the proof doesn't really give a hint on how to find it. So what you could always do is check all cases. With low degree polynomials this is not hard. For example, you list all the second degree polynomials:

X^2,~X^2 + 1,~X^2+X,~X^2 + X + 1

and you check whether they are irreducible. Only the last one is, so that's your polynomial. You can do the same with third degree, fourth degree, etc. To get beyond that is going to be difficult by hand. So you can always consult a computer algebra system like GAP http://www.gap-system.org Currently, people have also collected giant lists of irreducible polynomials, as no clever algorithm exists.

 

[lpetrich]

The number of degree-n irreducible polynomials for GF(p) is given by
$$ \frac{1}{n} \sum_{m \text{ div } n} \mu(n/m) p^m $$
where μ is the Moebius mu function: 0 if n has repeated prime factors, (-1)^(number of factors) if those factors are all unique.

That number gets big *very* quickly with increasing n; it tends to pⁿ/n. For GF(2): A001037 - OEIS

 

[mathwonk]

the usual way to proceed to prove existence of such a field, is to use the fact that the multiplicative group of such a field is cyclic, hence if q = p^n, the elements of the field all satisfy the polynomial X^q - X = 0. Conversely it is not hard to show that in any splitting field for that polynomial, the set of all its q (necessarily distinct) roots forms a field. see van der waerden's modern algebra, chapter 5 section 37. I don't know if this is as explicit as what you want, since your discussion goes along the lines of finding the minimal polynomial for a primitive element for this splitting field extension. This seems however like a fairly elementary proof of existence of such a field and hence of such a polynomial.