How to find all irreducible polynomials in Z2 with degree 5? I am totally lost on how to do this one. I am supposed to accomplish the following:
Find all irreducible polynomials in $\mathbb{Z}_2[x]$ with degree $5$. 
I may use the fact that x, $x+1$ and $x^2+x+1$ are the irreducibles of degree less than or equal to 2
If someone could provide a step by step explanation of how to do this, that would be amazing! Thanks in advance!
P.S.: This is not a homework, but is a question on a past exam that I couldn't answer and I want to know how to do it. 
 A: 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: 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$.
A: The following argument is specific to the question asked. Although I am
by no means a trained professional, please do not attempt this at home with
polynomials of larger degree.
The irreducible polynomial must be of the form
$x^5 + a_4x^4 + a_3x^3 + a_2x^2 + a_1x + 1$, that is, the degree-$5$ term
as well as the constant term must be nonzero. Of the $16$ possible
choices of $(a_4,a_3,a_2,a_1)$ we can eliminate the $8$ vectors of
even Hamming weight because the corresponding degree-$5$ polynomials 
have $1$ as a root. So, we are down to $8$ polynomials of which 
$6$ are necessarily
irreducible because the $30$ elements of $\mathbb F_{32}-\mathbb F_2$
all have order $31$ and come in sets of $5$ conjugates. Starting with
the lexicographically first polynomial $x^5 + x + 1$, we readily
discover via long division that
$$x^5 + x + 1 = (x^2+x+1)(x^3+x^2+1)$$ 
and so $x^5 + x + 1$ and its reciprocal $x^5+x^4+1 = (x^2+x+1)(x^3+x+1)$ 
are reducible polynomials. Thus, the irreducible polynomials of 
degree $5$ are
$$\begin{align}
x^5+x^2+1 &\quad x^5+x^3+1\\x^5+x^3+x^2+x+1 &\quad x^5+x^4+x^3+x^2+1\\
x^5+x^4+x^2+x+1 &\quad x^5+x^4+x^3 + x + 1
\end{align}$$
A: 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.
