Factoring x^{16}-x in F_8[x] and Proving Equivalency in F_2[x]

[R.P.F.]

Homework Statement

Factor $$x^{16}-x$$ in $$F_8[x]$$

Homework Equations

The Attempt at a Solution

I know how to do it in $$F_2[x]$$. I also feel the factorizations are the same in the two fields..but not sure how to prove it.

 

[micromass]

How would you approach this question in $$\mathbb{F}_2[X]$$?? Also think about which parts of this approach do and do not carry over to $$\mathbb{F}_8[X]$$??

 

[R.P.F.]

How would you approach this question in $$\mathbb{F}_2[X]$$?? Also think about which parts of this approach do and do not carry over to $$\mathbb{F}_8[X]$$??

$$q=p^r$$There is a theorem saying that the irreducible polynomials of $$x^q-x$$ over $$F_p[x]$$ where $$p$$ is a prime are the irreducible polynomials in $$F_p[x]$$ whose degrees divide $$r$$. So in $$F_2[x]$$ the poly is $$x(x-1)(x^2+x+1)(x^4+x^3+x^3+x+1)(x^4+x+1)(x^4+x^3+1)$$. I can show that in $$F_8[x]$$ the poly has no more linear factors than in $$F_2$$ but not sure how to deal with quadratics.

 

[micromass]

$$q=p^r$$There is a theorem saying that the irreducible polynomials of $$x^q-x$$ over $$F_p[x]$$ where $$p$$ is a prime are the irreducible polynomials in $$F_p[x]$$ whose degrees divide $$r$$. So in $$F_2[x]$$ the poly is $$x(x-1)(x^2+x+1)(x^4+x^3+x^3+x+1)(x^4+x+1)(x^4+x^3+1)$$. I can show that in $$F_8[x]$$ the poly has no more linear factors than in $$F_2$$ but not sure how to deal with quadratics.

OK, that's already good. Can you show now that the expression $$x(x-1)(x^2+x+1)(x^4+x^3+x^3+x+1)(x^4+x+1)(x^4+x^3+1)$$ is also the factorization in $$\mathbb{F}_8[X]$$. To do this, you have to show that no other polynomial in the expression factorizes. Let me give you an example how to do this:

Consider $$x^2+x+1$$, if it factorizes in $$\mathbb{F}_8[X]$$, then it factorizes in linear factors. So, if it factorizes, then the polynomial $$x^2+x+1$$ must have a root in $$\mathbb{F}_8$$. This is not possible, because no element in $$\mathbb{F}_8$$ has degree 2.
Try to do something for the other polynomials...

 

[R.P.F.]

OK, that's already good. Can you show now that the expression $$x(x-1)(x^2+x+1)(x^4+x^3+x^3+x+1)(x^4+x+1)(x^4+x^3+1)$$ is also the factorization in $$\mathbb{F}_8[X]$$. To do this, you have to show that no other polynomial in the expression factorizes. Let me give you an example how to do this:

Consider $$x^2+x+1$$, if it factorizes in $$\mathbb{F}_8[X]$$, then it factorizes in linear factors. So, if it factorizes, then the polynomial $$x^2+x+1$$ must have a root in $$\mathbb{F}_8$$. This is not possible, because no element in $$\mathbb{F}_8$$ has degree 2.
Try to do something for the other polynomials...

Yeah I know how to show that there are no more linear factors but quadratics are giving me trouble. I do not see how to see the degree-4 factors cannot be factored into two quadratics..hints please?

 

[postylem]

I do not see how to see the degree-4 factors cannot be factored into two quadratics

Note that the polynomial factors completely into linears over $\mathbb{F}_{16}$. Notice that $\mathbb{F}_8$ is a degree 3 extension of $\mathbb{F}_2$, and $\mathbb{F}_{16}$ is a degree 4, and $\gcd(3,4)=1$. That should get you started.