Irreducible polynomials of degree 3 and 5

Question

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:

$x^3$

$x^3+1$

$x^3+x$

$x^3+x+1$

$x^3+x^2$

$x^3+x^2+1$

$x^3+x^2+x$

$x^3+x^2+x+1$

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?

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$.

Application:

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.