1. ## Finite fields

Hi!
I need help for solve this problem:
Construct a field with four elements by adjoining a suitable root of x4-x to Z2

Tks..

2. ## Re: Finite fields

Originally Posted by charles01
Hi!
I need help for solve this problem:
Construct a field with four elements by adjoining a suitable root of x4-x to Z2

Tks..
$x^4 - x = 0$ has solutions
x = 0 or $x^3 -1 = 0$

$x = 0,~1,~\frac{-1 + i \sqrt{3}}{2},~\frac{-1 - i \sqrt{3}}{2}$

-Dan

3. ## Re: Finite fields

The new possibilities are $(-1+i\sqrt 3)/2$ and $(-1-i\sqrt 3)/2$?? but their product is zero in Z2.

Tks

4. ## Re: Finite fields

Originally Posted by charles01
The new possibilities are $(-1+i\sqrt 3)/2$ and $(-1-i\sqrt 3)/2$?? but their product is zero in Z2.

NO! the product is 1. The product of two conjugates is never zero unless they are zero.

5. ## Re: Finite fields

Originally Posted by topsquark
$x^4 - x = 0$ has solutions
x = 0 or $x^3 -1 = 0$

$x = 0,~1,~\frac{-1 + i \sqrt{3}}{2},~\frac{-1 - i \sqrt{3}}{2}$

-Dan
this makes no sense at all: 1/2 is undefined in a field of characteristic 2 (such as Z2).

instead, let's factor x4 - x into irreducible factors:

x4 - x = x(x - 1)(x2 + x + 1)

it is obvious that the linear factors x and x - 1 are irreducible (and have the roots x = 0 and x = 1 in Z2), to show that x2 + x + 1 is irreducible over Z2, it is sufficent to show it has no linear factors, that is: no roots in Z2:

02 + 0 + 1 = 0 + 1 = 1 ≠ 0
12 + 1 + 1 = (1 + 1) + 1 = 0 + 1 = 1 ≠ 0.

let u be a root of x2 + x + 1. just to be clear, what we are REALLY doing is taking the quotient ring:

Z2[x]/(x2 + x + 1), the ring of ALL polynomials in Z2, modulo the ideal generated by the polynomial x2 + x + 1.

we embed the field Z2 in this quotient by mapping a to the coset a + I (where we are taking I = (x2 + x + 1) because i'm lazy and hate typing a polynomial over and over again), for any element a in Z2 (there's only 2 of them)).

in this quotient ring u is the coset of x. it is clear that this actually gives a root:

u2 + u + 1 = (x + I)2 + (x + I) + (1 + 1) = (x2 + I) + (x + I) + (1 + I) = x2 + x + 1 + I = I = 0 + I, since x2 + x + 1 is IN I.

since it's tiresome to keep running "+I" after everything, we'll drop it (just remember that "a" means a+I, and "u" means x+I).

now in our new quotient ring, we have just 4 distinct cosets:

I = 0 + I (the identity of the ring Z2[x]/I), which we are just going to call "0".
1 + I , which we are just going to call "1" (this is indeed the multiplicative identity of Z2[x]/I, verify this!).
x + I, which we are going to call "u"
(x+1) + I, which we are going to call "u+1".

note that for any polynomial of degree 2 or more, say f(x), we can turn it into one of the 4 cosets above by writing:

f(x) = q(x)(x2 + x + 1) + r(x), where deg(r) < 2, or r = 0 whence:

f(x) + I = (q(x) + I)(I) + (r(x) + I) = r(x) + I (since I is the "0" of the ring Z2/I).

and the polynomials 0,1,x, and x+1 are the only elements of Z2[x] of degree < 2, together with 0.

now, we can use some "high-powered" ring theory, to establish that {0,1,u,u+1} is a field by showing that (x2+x+1) is a maximal ideal, because x2+x+1 is irreducible over Z2, but we can just show that our 4-element set is a field DIRECTLY.

it is immediate that Z2[x]/I is a ring, being a quotient ring. so we only need to verify that the set {1,u,u+1} forms a group under multiplication.

since we already know (since we're in a ring) the multiplication is associative, we only need to show closure, and inverses.

before we start:

since u is a root of x2 + x + 1, we know that u2 + u + 1 = 0, hence u2 = -(u + 1) = u + 1 (since we are in a ring of characteristic 2).

now:

(1)(1) = 1
(1)(u) = u
(1)(u+1) = u+1

(u)(u) = u2 = u+1
(u)(u+1) = u2+u = (u+1)+u = (u+u)+1 = 0+1 = 1

(these are all the products we need to check, since Z2[x] is a commutative ring, hence so is Z2[x]/I).

thus we have closure.

finally, we see that:

(1)(1) = 1, so 1 has an inverse (itself).
(u)(u+1) = 1, so u and u+1 are inverses of each other.

note that we could, if we desired, write {1,u,u+1} as {1,u,u2}, that is u is a generator for this group and:

u3 = (u)(u2) = (u)(u+1) = 1, so u is of order 3, while:
(u+1)3 = (u+1)(u+1)2 = (u+1)(u2+1) = (u+1)((u+1)+1) = (u+1)(u) = 1, so u+1 is ALSO of order 3.

this is no accident, the non-zero elements of a finite field ALWAYS form a cyclic group. in this case, u is a "primitive element" of our field of four elements.

6. ## Re: Finite fields

Thank you so much for the help Deveno!