Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 ?

share|improve this question
    
I am reasonably sure you want $F[\alpha] \setminus \{0\}$ and not $F[\alpha]\{0}$...Do you want the latter unrenderable version? –  user21436 May 1 '12 at 16:50
    
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. –  Jyrki Lahtonen May 1 '12 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.

share|improve this answer

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?

share|improve this answer
    
So $\alpha$ has order 9 ? –  Kiv Efehe May 1 '12 at 16:57
    
@KivEfehe: Correct. Well done! –  Jyrki Lahtonen May 1 '12 at 16:57
    
Yay ! Not sure I know how to rewrite. $\alpha^3(\alpha^3+1)$. Why would this help?? –  Kiv Efehe May 1 '12 at 17:05
1  
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 :-) –  Jyrki Lahtonen May 1 '12 at 17:08
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? –  Jyrki Lahtonen May 1 '12 at 18:17

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.