How can I factor the polynomial $x^7-1$ in GF(2)?

Question

The result is $(x+1)(x^3+x+1)(x^3+x^2+1)$, but I don't understand how I can calculate it.

Answer 1

In the reals, $x^7-1=(x-1)(x^6+x^5+x^4+x^3+x^2+x+1)$, so that is true in $GF(2)$ as well. Then $x-1=x+1$ Now we have to factor the second term. The degrees of the factors need to add to $6$ and both factors must include $+1$. That doesn't leave many to try. If we guess that we have two cubics, we have $(x^3+?x^2+?x+1)(x^3+?x^2+?x+1)=x^6+x^5+x^4+x^3+x^2+x+1$ To get the $x^5$ term we need one of the squares to be $1$ and the other zero, so we have $(x^3+x^2+?x+1)(x^3+?x+1)=x^6+x^5+x^4+x^3+x^2+x+1.$ To get the $x$ term one of the linear factors must be $1$ and the other zero-leaving two possibilities.

Answer 2

It easy to see that 1 is the only root of $x^7-1$ in $GF(2)$. So $x^7-1=(x-1)(x^6+x^5+\cdots +1)$. Now suppose $f=x^6+\cdots+1$ is reducible. Let $f_1$ be a irreducible factor of $f$ with minimal degree. Then $deg(f_1)=2$ or $3$. But it is easy to find all the irreducible polynomials of degree $\le 3$(hint: polynomial $g$ such that $2\le deg(g) \le 3$ is irreducible if and only $g$ has a root.)