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

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?

• you mean in $\mathbb{F}_2[x]$ ? – reuns Apr 29 '16 at 2:12
• Think about powers mod 2, and you can simplify this a bunch. – Davey Apr 29 '16 at 2:12
• wiki/Factorization_of_polynomials_over_finite_fields – reuns Apr 29 '16 at 2:16
• Both 0 and 1 are not root, seems like this polynomial is irreducible. But I'm not sure. – Kelan Apr 29 '16 at 2:17
• and since it is of degree $6$ all you have to do is proving it is not divisible by any degree $2$ and $3$ polynomial : – reuns Apr 29 '16 at 2:18

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.
• This is a classical and very general result: the polynomial $X^{p^{n}} - X$ is always the product of all irreducible polynomials of degree dividing $n$ over the field $\mathbb{F}_{p}$. There are many resources for this particular result, including some on this site. – Alex Wertheim Apr 29 '16 at 2:22