How to find all irreducible polynomials in Z2 with degree 5? [duplicate]

Here's a different take. A bit ad hoc, but to an extent I expect that here. Also I will be using several bits and pieces of finite field theory.

Claim 1. $p_1(x)=p(x)=x^5+x^2+1$ is irreducible.

Proof. $p(0)=p(1)=1$ so it has no linear factors. That leaves the sole quadratic irreducible $x^2+x+1$ as a possibility. But $x^3+1=(x^2+x+1)(x+1)$, so $$ p(x)=x^2(x^3+1)+1\equiv1\pmod{x^2+x+1}. $$ Thus $p(x)$ has no factors of degree $\le2$. QED

Corollary 1. $p_2(x)=p(x+1)=(x+1)^5+(x+1)^2+1=x^5+x^4+x^2+x+1$ is irreducible.

Proof. A linear substitution takes an irreducible to an irreducible. QED

Fun fact. If $q(x)$ is irreducible with non-zero constant term(over any field), then so is its reciprocal polynomial $$\tilde{q}(x)=x^{\deg q}q(\frac1x).$$

Proof. If we had $\tilde{q}(x)=g(x)h(x)$, it is an easy exercise to see that we would also have $q(x)=\tilde{g}(x)\tilde{h}(x)$. QED

Therefore $$ p_3(x):=\tilde{p_1}(x)=x^5+x^3+1 $$ and $$ p_4(x):=\tilde{p_2}(x)=x^5+x^4+x^3+x+1 $$ are also irreducible.

Going back to linear substitutions we see that $$ p_5(x):=p_3(x+1)=x^5+x^4+x^3+x^2+1 $$ is irreducible, and so is its reciprocal $$ p_6(x):=\tilde{p_5}(x)=x^5+x^3+x^2+x+1 $$ which incidentally coincides with $p_4(x+1)$.

At this point we need another bit of theory. All these six polynomials have five zeros in the field $\Bbb{F}_{32}$, so between them they are minimal polynomials of all the thirty elements that are not in the prime field. Thus there are no others, and the list is complete.

I don't recall having done this exercise ever before, so thanks for letting me do it. I knew in advance that $p_1(x)$ is irreducible, because that occurs frequently enough. I also knew that there would be exactly six irreducible quintics. I also knew that the substitutions $x\to 1/x$ and $x+1$ generate a group of six automorphisms of the rational function field. This time the stabilizer was trivial, so finding one irreducible produced all six.

Here is a rough procedure for finding all irreducible polynomials in $\mathbb{Z}_{2}[x]$. I will leave some of the details of computation to you.

If we let $f(x) = x^{5}+a_{4}x^{4}+a_{3}x^{3}+a_{2}x^{2}+a_{1}x+a_{0} \in \mathbb{Z}_{2}[x]$, we see that each $a_{i}$ can be $0$ or $1$, yielding two choices for each of the five coefficients. Hence, we note that there are $32$ polynomials of degree $5$ in $\mathbb{Z}_{2}[x]$.

Now, for $f(x)$ to be irreducible, it cannot be divisible by any polynomial in $\mathbb{Z}_{2}[x]$ of degree $<5$. If a product of polynomials $\prod_{i} g_{i}(x)$ has degree $5$, then it follows that the degree of at least one $g_{i}(x) < 3$ (another way of saying this is that the any partition of $5$ into a sum of strictly positive integers contains a summand $ < 3$). Hence, it suffices to find all $f(x) \in \mathbb{Z}_{2}[x]$ of degree $5$ such that no irreducible polynomial of degree $1$ or $2$ divides $f(x)$.

It is straightforward to test for division by the polynomials of degree $1$. We must ensure that our $f(x)$ does not have any roots in $\mathbb{Z}_{2}$. Simply take a test $f(x)$ and verify that $f(0)$ and $f(1)$ are nonzero. This narrows down our set of $16$ polynomials to our remaining possible choices. Call this remaining set $P$.

Now, to test for division by irreducible polynomials of degree $2$, we must first compute the irreducible polynomials of degree $2$ in $\mathbb{Z}_{2}[x]$. I leave this to you - comment if you need further help in this step. Once we have computed the irreducible polynomials of degree $2$, we can use simple polynomial long division (since $\mathbb{Z}_{2}[x]$ is a Euclidean domain!) to test each element of $P$ for divisibility by an irreducible polynomial of degree $2$. If $f(x) \in P$ is not divisible by any irreducible polynomial of degree $2$, it is an irreducible polynomial of degree $5$ in $\mathbb{Z}_{2}[x]$. I leave the details of these actual computations to you. Feel free to comment if you need further hints!

A straightforward inductive way to do this is to list all reducible polynomials of degree 5 and taking the complement set.

The list of reducible polynomials can be obtained by multiplying polynomials of degrees $a$ and $b$ such that $a+b=5$ in all the possible ways.

Since a polynomial will always factor into irreducibles, some shortcuts can be taken in the described strategy once you know the irreducible polynomials of degree $<5$.