I am taking all the irreducible polynomials over $\mathbf{F}_2$ of degree 1 to 4 inclusive and using the long division to determine whether the given $f$ is divisible by anyone of them and it is not so.

What are the other ways?

  • 5
    $\begingroup$ Your method may well be the best way. The only other thing that comes to mind is to show (compute) $gcd(f, x^{16}-x) = 1$, as every irreducible polynomial of degree dividing dividing $4$ over $\mathbb{F}_{2}[x]$ divides $x^{16}-x$. Then you can check the remaining irreducible polynomials of degree $3$, but that's all that I can think of. $\endgroup$ Dec 29, 2013 at 22:22
  • 1
    $\begingroup$ Agree with AWertheim. If you want to check both irreducible cubics in one go, you can similarly calculate $\gcd(f,x^8-x)$. Here $f-(x^8+x)=x^7+x^3+1$ that I recognize as my favorite low weight primitive (hence irreducible) polynomial of degree 7, so it is already clear that $\gcd(f,x^8-x)=1$. $\endgroup$ Dec 29, 2013 at 22:46
  • $\begingroup$ There are immediate observations that would speed up checking divisibility by irreducible quartics: $x^{5+n}+x^n$ is divisible by the fifth cyclotomic, so $f$ has a quadratic remainder $f+(x^3+x^2)(x^5+1)$ modulo $x^4+x^3+x^2+x+1$. Similar "pattern matching" shows right away that $f+(x^4+1)(x^4+x^3+1)=x$ and $f$ being almost palindromic simplifies checking non-divisibility by the reciprocal $x^4+x+1$ a bit. The quadratic irreducible is a factor of $x^3+1$, but both $x^3+1$ and $x^7+x=x(x^6+1)$ are divisible by that... $\endgroup$ Dec 29, 2013 at 22:55
  • $\begingroup$ There’s no problem with irreducible cubic factors, is there? If such a polynomial divided $f$, then its root $\rho$ (a primitive seventh root of unity) would be a root of $f$. But then $\rho^8+\rho^7+\rho+1=0$, and $f(\rho)=\rho^3\ne0$. $\endgroup$
    – Lubin
    Dec 30, 2013 at 0:21
  • $\begingroup$ Correct, @Lubin. I noticed that after it was a bit too late to fix the comment. And I also knew that particular irreducible heptic :-). Well, Bill Dubuque seems to have handled it that way as well, and it is admittedly a better way. $\endgroup$ Dec 30, 2013 at 13:57

1 Answer 1


This can be done quickly by the Euclidean algorithm. If $f$ is reducible it has an irreducible factor of degree $\le 4,\,$ so either it has a factor in common with $\, x^{16}-x\,$ (which is divisible by every irreducible of degree dividing $4$) or, it has cubic factor, hence a factor in common with $\,x^8-x,\,$ hence a factor in common with $\, g =x^7-1,\,$ since $\,x\nmid f.\,$

The latter case is impossible, since $\,f\ {\rm mod}\ g = f - (x+1)(x^7\!-1) = x^3,\,$ thus $\,(f,g) = (f\ {\rm mod}\ g,\,g) = (x^3,g) = 1\,$ by $\,(x,g)= (x,x^7\!-1) = (x,-1)= 1.$

For the first case, by $\,x\nmid f,\,$ it suffices to show that $\,f\,$ is coprime to $\,g = x^{15}\!-1.$

Division $ $ yields $\ \ g\ {\rm mod}\ f = x^6\!+x^4\!+x^2 = x^2 h^2,\ \ h = x^2\!+x+1 $

Hence $\ \ (g,f) = (g\ {\rm mod} f,\, f) = (x^2 h^2,f)$ so it suffices to show $(h,f) = 1,\ $ since $\,x\nmid f$.

Indeed $\,(h,f) = (h,\, f\ {\rm mod}\ h) = (h,x\!-\!1) = (h(1),x\!-\!1)=(1,x\!-\!1)=1$.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .