2
$\begingroup$

The following is a theorem I am trying to understand.

If $n$ is a positive integer and $m=2*3^{n-1}$
We know that $t^m+t^{m/2}+1$ is irreducible over GF(2).

I am looking at the case when $n=2, m=6$: so $f(t)=t^6+t^3+1$

Q1. What are the basic features of the corresponding extension field $F[\alpha]$ of F?

Since we are working in $GF[2]$, $F[\alpha]$ has $(2^6)$ elements. But obviously $64-1$ ($F[\alpha ] \setminus \{0\}$) is not prime, so can't use Lagrange's theorem about primitive to calculate the order of $F[\alpha]$. How do I go about calculating that?

Q2. How do I expres $(1+\alpha)^{-1}$ as an F-linear combination of $1,\alpha,\alpha^2,...,\alpha^5$ ?

since $\alpha^6=\alpha^3+1$ here, solve $(1-\alpha)\sum(a_i\alpha^i)=1$

I get: $a_0 + a_5 = 1$
$a_0 + a_1 = 0$
$a_1 + a_2 = 0$
$a_2 + a_3 + a_5 = 0$
$a_3 + a_4 = 0$
$a_4 + a_5 = 0$

so $a_3=a_4=a_5=1$
and $a_0=a_1=a_2=0$

Can anyone go through my working and suggest things that can be improved, finished or missing? or even direct me to a book where i can read more about this ?

  • 0
    In case you are wondering about the theorem itself, [here's a proof](http://math.stackexchange.com/a/70159/11619) I wrote as an answer to another question on this site. That is an exercise in *Finite Fields* by Lidl & Niederreiter - the tome of finite fields.2012-05-01

2 Answers 2

1

Since $\alpha$ is a root of $t^6 + t^3 + 1$, that is, $\alpha^6 + \alpha^3 + 1 = 0$ and we are working in a field of characteristic $2$, we have $\alpha^6 = \alpha^3 + 1 \Rightarrow \alpha^9 = \alpha^3(\alpha^3 + 1) = \alpha^6 + \alpha^3 = 1.$ So, $\alpha$ is an element of order $9$ or a divisor thereof. But $\alpha$ cannot have order $3$ since $\alpha^3 = \alpha^6 + 1 \neq 1$ and so $\alpha$ has order $9$.

The standard way of solving problems of the type of Q2 is to use the extended Euclidean algorithm to express $1$, the gcd of $1+t$ and $t^6 + t^3 + 1$, as a linear combination of the two polynomials, that is, compute $a(t)$ and $b(t)$ of degrees less than $6$ such that $a(t)(1+t) + b(t)(t^6 + t^3 + 1) = 1.$ This is called Bezout's identity.

0

A mixture of hints and other bits.

Q1: Your first claim is correct. $F[\alpha]=GF(64)$. I assume that your question is about the order of $\alpha$. The big hint is that the irreducibility of $\phi(t)=t^6+t^3+1$ depends on the fact that $\phi(t)$ is a cyclotomic polynomial (at least the proof of irreducibility that I am thinking about depends on that piece of information). Which cyclotomic polynomial is it? What does that tell you about the order of its roots?

Q2: [Edit] Your solution looks good to me. Here's another way of going about it:[/Edit] $ 1=\alpha^6+\alpha^3=\alpha^3(\alpha^3+1). $ Can you write the right hand side in the form $(1+\alpha)$ times something?

  • 1
    Didn't you determine that $|F[\alpha]|=64$ at the beginning? What do you mean by 'order of $F[\alpha]$'?? I thought that was a misprint, and you wanted the order of $\alpha$. The order of a group is the number of its elements, and therefore the order of $F[\alpha]$ is 64. Somehow I think that you mean something else?2012-05-01