Factor $x^6+x^5+x^4+x^3+x^2+x+1$ in $\mathbb{F}_2[x]$

Question

I'm trying to factor $x^6+x^5+x^4+x^3+x^2+x+1$ in $\mathbb{F}_2[x]$. But I don't know how to do that. Anyone can tell whether there is a nice way to solve all these kinds of problems?

Answer 1

Well, in general, one usually recursively builds irreducible polynomials of low degree via Euclidean division. But in this case, there is a very nice trick: let $P(X) = X^6+X^5+X^4+X^3+X^2+X+1$. Then it is not hard to show that $P(X)(X+1) = X^7+1$ (one can either compute this directly, or think of the analagous result for truncated geometric series). But then $P(X)(X+1)(X) = X^8+X = X^{2^3}+X$, which is the product of all irreducible polynomials of degree dividing $3$ over $\mathbb{F}_{2}$. So $P(X)$ must factor as the product of the unique two irreducible polynomials of degree $3$ over $\mathbb{F}_{2}$. I leave it to you to compute these; feel free to comment if you need more help.