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

Solution 1:

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$

Solution 2:

The tricky way to do this is to realize that if $p(x)$ is prime polynomial of degree $n$, then ${\mathbb{Z}_2[z]}/{p(z)}$ is a field of order $2^n$ and hence for every element $a$ of the field, $\ a^{2^n}-a = 0$. In particular, then, $z^{2^n}-z$ must be divisible by $p(z)$. Now, $z^{2^n}-z$ is also divisible by any prime polynomial of degree $d|n$, so we first have to factor those out, and then you get the product of the primes of degree $n$.

In particular, $x^8-x$ must be a product of the primes of degree one and the primes of degree $3$. We can easily factor out $x(x+1),$ and we see that the primes of degree $3$ must multiply together to get $x^6+x^5+x^4+x^3+x^2+x+1$. So you can test for primeness of a polynomial of degree $3$ by seeing if it divides into this polynomial.

Similarly, for $n=4$, you have $x^{16}-x$ must be the product of the primes of degrees $1,2$ and $4$. The only prime of degree $2$ is $x^2+x+1,$ so the product of the primes of degree $4$ must be $\dfrac{x^{16}-x}{(x^2+x+1)x(x+1)}\ =\ 1 + x^3 + x^6 + x^9 + x^{12}\:.\ $ So we know that there are $3$ primes of order $4$.

Finally, the products of the primes of degree $5$ must be $\ \dfrac{x^{32}-x}{x(x+1)}\ =\ 1 + x + x^2 +\:\cdots\: + x^{30}$.

Note that the primes of degree $3$ have to be $x^3+x+1$ and $x^3+x^2+1$. That's because if $p(x)$ is prime, then $p(1)=1$ and $p(0)=1$. So we have to have $x^3$ and $1$ as terms f $p(x)$, and we have to have an odd number of non-zero terms in $p(x)$.