Question about field with 8 elements
John
that x^3 = x + 1.
Any hints ?
Tonico
Since f(y):= y^3 + y + 1 is irreducible in F_2[y] , with F_2 = Z/2Z,
we get that H:= F_2[y]/<f(y)> is a field with 8 elements, and
thus H ~ K since there's a unique field with p^n elements for every
positive integer n and any prime p.
Thus, as y':= y + <I> in H is an element s.t. y'^3 + y' + 1 = 0 <==>
y'^3 = y' + 1 (remember we're working modulo 2 here) , if q is
isomorphism between H and K, then x:= q(y') is the element you're
looking for in K.
Tonio
achille
Another way to prove the assertion:
Notice for any finite field F of n elements, elements
of F are roots of the polynomial x^n - x = 0. For our
field K with 8 elements, we have for all x in K,
x^8 - x = x(x-1)(x^6+x^5+x^4+x^3+x^2+x+1) = 0
This implies for all x in K differs from 0 and 1,
x^6 + x^5 + x^4 + x^3 + x^2 + x + 1 = 0
Now let f(y) := y^3 + y + 1. Notice over Z/2Z, the base
field of K, we have:
f(x^2 + x) = x^6+3*x^5+3*x^4+x^3+x^2+x+1
= x^6+x^5+x^4+x^3+x^2+x+1
This means if one pick any element x from K differ from 0
and 1, y = x^2 + x will be a root of f(y) = 0. ie.
f(y) = 0 has a root in K.
Actually, one can do better than this.
Since char(K) = 2, the map phi : x -> x^2 + x is a vector
space homomorphism when one view K as a vector space over
Z/2Z. We have:
ker(phi) = {0,1}
=> dim ker(phi) = 1
=> dim im(phi) = dim K - dim ker(phi) = 3-1 = 2
=> | im(phi) | = 2^2 = 4
=> | phi(K \ {0,1}) | = | im(phi)\{0} | = 3
This implies f(y) = 0 has exactly 3 roots in K.
Tim Little
Have you seen the proof that there is only one field (up to
isomorphism) of p^n elements for given positive integer n and prime p?
--
Tim
quasi
wrote:
>Let K be commutative field with 8 elements. Prove there is
>x in K such that x^3 = x + 1.
The multiplicative group of K has order 7, so
x^7 = 1
for all nonzero elements of K.
Let a(x) = (x^7-1) / (x-1)
= x^6 + x^5 + x^4 + x^3 + x^2 + x + 1.
Then all elements of K other than 0,1 satisfy a(x) = 0.
Let b(x) = x^3 - x - 1.
By long division,
a(x) = q(x)b(x) + r(x)
where
q(x) = x^3 + x^2 + 2x + 3
r(x) = 4x^2 + 6x + 4
Reducing mod 2,
a(x) = (x^3 + x^2 + 1) b(x)
But a(x) has 6 roots, so b(x) must have 3 roots in K.
It follows that there are 3 elements of K such that
x^3 = x + 1
Remarks:
(1) My argument is essentially the same as achille's.
(2) Tonico's argument gets right to the heart of the matter.
quasi
John
Bill Dubuque
> On Mar 26, 8:20 am, Tonico <Tonic...@yahoo.com> wrote:
>> On Mar 26, 2:48 am, John <to1m...@yahoo.com> wrote:
>>>
>>> Let K be commutative field with 8 elements.
>>> Prove there is x in K such that x^3 = x + 1.
>>
>> we get that H:= F_2[y]/<f(y)> is a field with 8 elements, and
>> thus H ~ K since there's a unique field with p^n elements for every
>> positive integer n and any prime p.
>>
>> Thus, as y':= y + <I> in H is an element s.t. y'^3 + y' + 1 = 0 <==>
>> y'^3 = y' + 1 (remember we're working modulo 2 here) , if q is
>> isomorphism between H and K, then x:= q(y') is the element you're
>> looking for in K.
>
>
> Notice for any finite field F of n elements, elements
> of F are roots of the polynomial x^n - x = 0. For our
> field K with 8 elements, we have for all x in K,
>
> x^8 - x = x(x-1)(x^6+x^5+x^4+x^3+x^2+x+1) = 0
>
> This implies for all x in K differs from 0 and 1,
>
> x^6 + x^5 + x^4 + x^3 + x^2 + x + 1 = 0
>
> Now let f(y) := y^3 + y + 1. Notice over Z/2Z, the base
> field of K, we have:
>
> f(x^2 + x) = x^6+3*x^5+3*x^4+x^3+x^2+x+1
> = x^6+x^5+x^4+x^3+x^2+x+1
>
> This means if one pick any element x from K differ from 0
> and 1, y = x^2 + x will be a root of f(y) = 0. ie.
>
> f(y) = 0 has a root in K.
>
> Actually, one can do better than this.
>
> Since char(K) = 2, the map phi : x -> x^2 + x is a vector
> space homomorphism when one view K as a vector space over
> Z/2Z. We have:
>
> ker(phi) = {0,1}
> => dim ker(phi) = 1
> => dim im(phi) = dim K - dim ker(phi) = 3-1 = 2
> => | im(phi) | = 2^2 = 4
> => | phi(K \ {0,1}) | = | im(phi)\{0} | = 3
>
> This implies f(y) = 0 has exactly 3 roots in K.
One can give a simpler direct proof that does not require any knowledge
of field theory. By Lagrange's theorem, the 7 nonzero elts of K are all
roots of x^7 - 1. So if we show x^7-1 = (x^3+x+1) f(x) then we infer
x^3+x+1 has 3 roots in K (else f(x) of degree 4 has more than 4 roots).
A simple modular calculation shows that x^3+x+1 divides x^7-1 over Z/2
mod x^3+x+1: x^7 = x(x^3)^2 = x(x+1)^2 = x(x^2+1) = x^3+x = 1 QED
--Bill Dubuque