Irreducible polynomials of degree 3 and 5 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?
 A: 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:


*

*$0$ should be no root $\Leftrightarrow$ the constant coefficient is $1$.

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


*

*$x^2+x+1$,

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

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