Math Is Fun Forum

freddogtgj

Member

Registered: 2006-12-02

Posts: 54

Algebra Question: Help Needed!

This is the question i have:

Let F = {0,1} denote the field of integers mod 2.
Show that the polynomial x^3+x+1 is irreducible over F.
Hence construct a field with eight elements. (You should write down the addition
and multiplication tables of your field.)

Could someone help me on this?

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: Algebra Question: Help Needed!

Show that the polynomial x^3+x+1 is irreducible over F.

To show that a polynomial is irreducible, we must show that it can't be broken up into two polynomials being multiplied together.  So lets do the opposite, lets assume that it can be.  Then what can we say about the two polynomials which are being multiplied together?  Simply that their degree must be less than 3.

Simply list ever polynomial out:

0x^2 + 0x + 0 = 0
0x^2 + 0x + 1 = 1
0x^2 + 1x + 0 = x
0x^2 + 1x + 1 = x + 1
1x^2 + 0x + 0 = x^2
1x^2 + 0x + 1 = x^2 + 1
1x^2 + 1x + 0 = x^2 + x
1x^2 + 1x + 1 = x^2 + x + 1

But this is ugly.  So lets try to make the problem a bit simpler.  If there are polynomials f, g, and h such that:

f = gh

Then it must be that

deg(f) = deg(g) + deg(h)

So what numbers add up to 3?  0 + 3 and 1 + 2.  Well, obviously we can eliminate 0 + 3.  So we are left with 1 + 2.  That is, if this polynomial is reducible, it has a factor of degree 1.  So all we need to check are:

x
x + 1

And if these don't factor it, you're done.  There are two ways to show that they are not factors.  In general, you can divide your degree 3 polynomial by each of these and show there is a non-zero remainder.  But because these are degree 1, we can use a little trick:

x - c is a root of f(x) if and only if f(c) = 0.

So just plug compute f(0) and f(-1 = 1) (where f is your degree 3 poly), and as long as these are non-zero, they don't factor.

---

"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

freddogtgj

Member

Registered: 2006-12-02

Posts: 54

Re: Algebra Question: Help Needed!

Isn't it possible to have cubic factors as well?

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: Algebra Question: Help Needed!

Isn't it possible to have cubic factors as well?

Good question.  I hand waved this a bit here:

So what numbers add up to 3?  0 + 3 and 1 + 2.  Well, obviously we can eliminate 0 + 3.  So we are left with 1 + 2.

So let me go more into detail.  If there is a cubic factor, then the other factor will have to be of degree 0, as the sum of the degrees of the two polynomials must add up to 3.

But by irreducible, we are talking about being able to factor a polynomial into two non-constant polynomials.  This means that the degree of the two factors must be at least 1.

Does that make sense?

---

"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

freddogtgj

Member

Registered: 2006-12-02

Posts: 54

Re: Algebra Question: Help Needed!

Yea cheers make sense!