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^rThere 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^rThere 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.