Is there a clever way to decompose $f(X) = X^8 + X^7 + X^6 + X^4 + 1$ into irreducible factors over $\mathbb{Z}_2$? Or to see that it is irreducible itself?

This is what I have thought about so far: $f(0) \ne 0$ and $f(1) \ne 0$, so $f$ does not have linear factors. It also does not have quadratic factors, because the only irreducible quadratic polynomial over $\mathbb{Z}_2$, $X^2 + X + 1$, does not divide $f$. I could continue finding all irreducible polynomials of degree 3 and 4 and carrying out the corresponding polynomial divisions.

Is there a more clever solution?


Note that $(x^8+x^7+x^6+x^4+1)(x+1)=x^9 + x^6 + x^5 + x^4 + x + 1$. Thus, if $\alpha^5=1$, then $\alpha$ is a root of the latter polynomial. That is, the latter polynomial is divisible by $x^5+1=(x^4 + x^3 + x^2 + x + 1)(x+1)$. But this means that $x^4 + x^3 + x^2 + x + 1$ is a factor of your original polynomial. Now polynomial division leads us to

$$x^8+x^7+x^6+x^4+1=(x^4 + x + 1)(x^4 + x^3 + x^2 + x + 1).$$

It is easy to see that both fators on the RHS are irreducible over $\mathbb{Z}_2$. In fact, they have no roots in $\mathbb{Z}_2$ and are not divisible by $x^2+x+1$.

| cite | improve this answer | |
  • $\begingroup$ Neat, thank you! How did you know that multiplying by $X + 1$ would yield a useful polynomial? Is that a common trick in $\mathbb{Z}_2$? $\endgroup$ – bbrot Jan 7 '17 at 19:35
  • 1
    $\begingroup$ I started looking for roots $\alpha$, for which $\alpha^n=1$ (for some $n$). Since $x-1$ is always a factor of $x^n-1$, that led me to consider this multiplication. $\endgroup$ – math Jan 7 '17 at 20:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.