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 ?

  • $\begingroup$ I am reasonably sure you want $F[\alpha] \setminus \{0\}$ and not $F[\alpha]\{0}$...Do you want the latter unrenderable version? $\endgroup$
    – user21436
    May 1, 2012 at 16:50
  • $\begingroup$ In case you are wondering about the theorem itself, here's a proof 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. $\endgroup$ May 1, 2012 at 17:14

2 Answers 2


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.


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?

  • $\begingroup$ So $\alpha$ has order 9 ? $\endgroup$
    – Kiv Efehe
    May 1, 2012 at 16:57
  • $\begingroup$ @KivEfehe: Correct. Well done! $\endgroup$ May 1, 2012 at 16:57
  • $\begingroup$ Yay ! Not sure I know how to rewrite. $\alpha^3(\alpha^3+1)$. Why would this help?? $\endgroup$
    – Kiv Efehe
    May 1, 2012 at 17:05
  • 1
    $\begingroup$ What I had in mind was: $(\alpha^3+1)=(\alpha+1)(\alpha^2+\alpha+1)$, so $$ 1=\alpha^3(\alpha^3+1)=(1+\alpha)(\alpha^3+\alpha^4+\alpha^5), $$ but the method of your solution is guaranteed to work, whereas this is just a trick :-) $\endgroup$ May 1, 2012 at 17:08
  • 1
    $\begingroup$ 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? $\endgroup$ May 1, 2012 at 18:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .