How to factor this polynomial over $\mathbb{F}_2$

Question

On page 587 in Dummit and Foote, the authors say the polynomial $\frac{x^{16}-x}{x(x-1)(x^2+x+1)}$ can be factored into quartics over $\mathbb{F}_2$ as $(x^4+x^3+x^2+x+1)(x^4+x^3+1)(x^4+x+1)$.

I am having trouble seeing this. When I divide the polynomial $x^{16}-x$ by $x(x-1)(x^2+x+1)$ using long division, I get $x^{12}+x^9+x^6+x^3+1$. However, I am not sure how to factor this polynomial into quartics. How do I do this?

Answer 1

The Berlekamp algorithm gives $$ x^{16}-x=(x^4 + x^3 + x^2 + x + 1)(x^4 + x^3 + 1)(x^4 + x + 1)(x^2 + x + 1)(x + 1)x. $$ So the statement in Dummit and Foote is correct.

Answer 2

Over $\mathbb Z$ we have $$ \begin{align} x^{16}-x &= x(x^{15}-1) \\&= x \Phi_1(x) \Phi_3(x) \Phi_5(x) \Phi_{15}(x) \\&= x (x - 1) (x^2 + x + 1) (x^4 + x^3 + x^2 + x + 1) (x^8 - x^7 + x^5 - x^4 + x^3 - x + 1) \end{align} $$ and so your polynomial is $(x^4 + x^3 + x^2 + x + 1) (x^8 - x^7 + x^5 - x^4 + x^3 - x + 1)$.

You only need to factor $(x^8 - x^7 + x^5 - x^4 + x^3 - x + 1)$ mod $2$.