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.
On
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$.
On
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.
On
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}$$
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!