GF(3): Extending q(x) & Proving a is Not a Generator

[andrey21]

Describe how the field GF(3) may be extended by postulating the existence of a root a of q(x) and list all the elements of this larger field. Show that a is not a generator of the extended field.

q(x) = x²+1


My attempt

First replace x with a we obtain:

0 = a²+1
a²=-1
a²=2 (-1=2 in mod 3 numbers)

Take powers up to a^(3-1)=a²

a
a² = 2

No I'm sure I have proven a is not a generator but I am unsue how to calculate the elements.

 

[micromass]

Hi andrey21,

The exact mathematical notation for the thing you're trying to descirbe is \mathbb{F}_3[X]/(X^2+1). Thus elements of this field are just polynomails in \mathbb{F}_3, but with the additional property that X^2+1=0. This would also mean that X^3+X=0 for example.

Now, a general element in \mathbb{F}_3[X] is of the form a_nX^n+...a_1X+a_0. Can you reduce this polynomial to a simpler form using the relation X^2=-1?

 

[andrey21]

a₀+a₁X+a₂X²

Which can be written as:

a₀+a₁X+a₂(-1)

a₀+a₁X-a₂

 

[micromass]

So, what's the general form of elements in GF(3)?

 

[andrey21]

a₀+a₁X-a_n

 

[micromass]

So, if we have a_0+a_1X+a_2X^2, then we can always write it in the form a+bX for a,b in GF(3).

Is the same possible for general polynomials a_0+a_1X+...+a_nX^n?

 

[andrey21]

Ok so the elements for GF(3) are in the form ax+b for 0,1,2:

Giving:

0x+0
0x+1
0x+2
1x+0
1x+1
1x+2
2x+0
2x+1
2x+2

correct?

 

[micromass]

Looks good!

 

[andrey21]

Thank you micromass, so to conclude I can prove that a is not a generator as every element of GF(3) was not found when taking powers up to a²

 

[micromass]

Thank you micromass, so to conclude I can prove that a is not a generator as every element of GF(3) was not found when taking powers up to a²

That's not good enough. You've only calculated a and a². Nothing says that a³, a⁴,... cannot give all elements of GF(3). It doesn't, but you need to calculate a³, a⁴,... first.

 

[andrey21]

Ok so here's my revised answer:

a
a²=2
a³=2a
a⁴=2a²

=2(2)
=4
=1
Stop when get to 1, so every element is not found so a is not a generator.

 

[micromass]

That is good!

 

[andrey21]

Great Thank you micromass.

 

[andrey21]

Hi micromass I have another similar question which I am having some problems with:

p(x) = x²+3

GF(5) (0,1,2,3,4)
I must find all elements and decide if a is a generator or not.

First elements are:

0
1
2
3
4
x
x+1
x+2
.
.
.
4x+4

correct??

Now rewriting P(x) replacing x with a:

0=a²+3
a²=-3

a²=2 (-3=2 in mod 5 numbers)

 

[micromass]

Hi micromass I have another similar question which I am having some problems with:

p(x) = x²+3

GF(5) (0,1,2,3,4)
I must find all elements and decide if a is a generator or not.

First elements are:

0
1
2
3
4
x
x+1
x+2
.
.
.
4x+4

correct??

Now rewriting P(x) replacing x with a:

0=a²+3
a²=-3

a²=2 (-3=2 in mod 5 numbers)

That looks good already! So, now you need to calculate powers of a to see whether it is a generator...

 

[andrey21]

so here's my answer:

a
a²=2
a³=2a
a⁴=2a²
=2(2)
=4
a⁵=4a
a⁶=4a²
=4(2)
=8

since 8 is not a element of GF(5) should I stop here since I have proved every element will not be obtained.

 

[micromass]

But 8 is an element of GF(5). In GF(5), we have 8=3...