abstract algebra - Find all irreducible monic polynomials in $mathbb{Z}/(2)[x]$ with degree equal or less than 5

Find all irreducible monic polynomials in $\mathbb{Z}/(2)[x]$ with degree equal or less than $5$.

This is what I tried:

It's evident that $x,x+1$ are irreducible. Then, use these to find all reducible polynomials of degree 2. There ones that can't be made are irreducible. Then use these to make polynomials of degree 3, the ones that can't be made are irreducible. Repeat until degree 5.

Doing this way takes way too long and I just gave up during when I was about to reach degree 4 polynomials.

My question is: is there any easier way to find these polynomials?

P.S.: this is not exactly homework, but a question which I came across while studying for an exam.

Answer

Extrapolated Comments converted to answer:

First, we note that there are $2^n$ polynomials in $\mathbb{Z}_2[x]$ of degree $n$.

A polynomial $p(x)$ of degree $2$ or $3$ is irreducible if and only if it does not have linear factors. Therefore, it suffices to show that $p(0) = p(1) = 1$. This quickly tells us that $x^2 + x + 1$ is the only irreducible polynomial of degree $2$. This also tells us that $x^3 + x^2 + 1$ and $x^3 + x + 1$ are the only irreducible polynomials of degree $3$.

As hardmath points out, for a polynomial $p(x)$ of degree $4$ or $5$ to be irreducible, it suffices to show that $p(x)$ has no linear or quadratic factors. To rule out the linear factors, we can again throw out any polynomial not satisfying $p(0) = p(1) = 1$. That is, we can throw out any polynomial with constant term $0$, and we can throw out any polynomial with an even number of terms. This rules out $3/4$ of the polynomials. For example, the $4^{th}$ degree polynomials which do not have linear factors are:

• $ x^4 + x^3 + x^2 + x + 1 $


• $ x^4 + x^3 + 1 $


• $ x^4 + x^2 + 1 $


• $ x^4 + x + 1 $

The $5^{th}$ degree polynomials which do not contain linear factors are:

• $x^5 + x^4 + x^3 + x^2 + 1$



• $x^5 + x^4 + x^3 + x + 1$


• $x^5 + x^4 + x^2 + x + 1$


• $x^5 + x^3 + x^2 + x + 1$


• $x^5 + x^4 + 1$


• $x^5 + x^3 + 1$


• $x^5 + x^2 + 1$


• $x^5 + x + 1$

It still remains to check whether $x^2 + x + 1$ (which is the only quadratic irreducible polynomial in $\mathbb{Z}_2[x]$) divides any of these polynomials. This can be done by hand for sufficiently small degrees. Again, as hardmath points out, since $x^2 + x + 1$ is the only irreducible polynomial of degree $2$, it follows that $(x^2 + x + 1)^2 = x^4 + x^2 + 1$ is the only polynomial of degree $4$ which does not have linear factors and yet is not irreducible. Therefore, the other $3$ polynomials listed must be irreducible. Similarly, for degree $5$ polynomials, we can rule out

$$
(x^2 + x + 1)(x^3 + x^2 + 1) = x^5 + x + 1
$$

and

$$
(x^2 + x + 1)(x^3 + x + 1) = x^5 + x^4 + 1.
$$

The other $6$ listed polynomials must therefore be irreducible.

Notice that this trick of throwing out polynomials with linear factors, then quadratic factors, etc. (which hardmath called akin to the Sieve of Eratosthenes) is not efficient for large degree polynomials (even degree $6$ starts to be a problem, as a polynomial of degree $6$ can factor as a product of to polynomials of degree $3$). This method, therefore only works for sufficiently small degree polynomials.

To recap, the irreducible polynomials in $\mathbb{Z}_2[x]$ of degree $\leq 5$ are:

• $x$


• $x+1$



• $x^2 + x + 1$


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


• $x^3 + x + 1$


• $ x^4 + x^3 + x^2 + x + 1 $


• $ x^4 + x^3 + 1 $


• $ x^4 + x + 1 $


• $x^5 + x^4 + x^3 + x^2 + 1$


• $x^5 + x^4 + x^3 + x + 1$


• $x^5 + x^4 + x^2 + x + 1$


• $x^5 + x^3 + x^2 + x + 1$



• $x^5 + x^3 + 1$


• $x^5 + x^2 + 1$