Two part question:

1) There are three irreducible cubic polynomials $\mathbb F_2$

Aproach: Bruteforce, there are not as much cubic polynomials, just 8 of them:









Only three of them are irreducible(??): $x^3+1$,$x^3+x+1$ and $x^3+x^2+1$

Reality check - do i miss point of irreducible polynomial here, and should consider adding $x^3+x^2+x+1$ to irreducible list? It is reducible, bit different way then other polynomials: $x^3+x^2+x+1=(x+1)^3$

2) Only irreducible polynomial of degree 2 over $\mathbb F_2$ is $x^2+x+1$. Does it help, with conjuction of part 1, to find all irreducible polynomials of degree 5?


1 Answer 1


A polynomial in a field of degree two or three is irreducible if and only if it has no root. In $\mathbb F_2$ it is quite easy to check if a polynomial has a root:

  1. $0$ should be no root $\Leftrightarrow$ the constant coefficient is $1$.
  2. $1$ should be no root $\Leftrightarrow$ the number of non-zero coefficients is odd.

Both conditions can only be satisfied for non-constant polynomials if we have at least three non-zero coefficients. Five coefficients is too much for a polynomial of degree at most three. So we are looking for the polynomials with exactly three non-zero coefficients which are

  1. $x^2+x+1$,
  2. $x^3+x^2+1$,
  3. $x^3+x+1$.

In particular your polynomial $x^3+1$ is reducible since $1$ is a root.

Interesting side note:

Let $p,q$ be primes. It is quite easy to determine the number of irreducible polynomials in $\mathbb F_p[x]$ of degree $q$. Because each element in $\mathbb F_{p^q}\setminus \mathbb F_p$ is of degree $q$ and every irreducible polynomial of degree $q$ with leading coefficient $1$ is the minimal polynomial of exactly $q$ elements in $\mathbb F_{p^q}\setminus \mathbb F_p$ we get that the number of irreducible polynomials in $\mathbb F_p[x]$ of degree $q$ with leading coefficient $1$ is $$\frac{p^q-p}{q}.$$

So the total number of irreducible polynomials in $\mathbb F_p[x]$ of degree $q$ is $$\frac{(p^q-p)(p-1)}{q}$$ because we can multiply each of the former polynomials with one of the $p-1$ many units of $\mathbb F_p$.


Using this result we get for $p=2$ and $q=2,3,5$ that there are $$\frac{2^q-2}{q} = 1,2,6$$ irreducible polynomials of degree $q$ in $\mathbb F_2[x]$ which answers the question.

  • $\begingroup$ this is great info, thanks what about reducibility of degree 5? $\endgroup$ Sep 3, 2015 at 13:20
  • $\begingroup$ @TimoJunolainen See my edit. $\endgroup$ Sep 3, 2015 at 13:25
  • $\begingroup$ thanks a lot! feeling little fuzzy on subject, this clears a lot of things up $\endgroup$ Sep 3, 2015 at 13:35

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.