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

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.

marked as duplicate by Jyrki Lahtonen abstract-algebra StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); Oct 6 '18 at 14:59

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!

• This is a fine answer, although paragraph 3's phrasing is kind of awkward, since $f$ can always decompose as a product of more than two irreducibles; it is true that any reducible $f$ has some decomposition into factors of degrees 1+4 or 2+3 (or more broadly, that it's divisible by some irreducible polynomial of degree 1 or 2), but I think there's a better way of making that argument than your current phrasing. – Steven Stadnicki Oct 30 '14 at 17:41
• @StevenStadnicki: great points, thanks! I'll try to edit it to something better. :) – Alex Wertheim Oct 30 '14 at 17:42
• @StevenStadnicki: I've updated paragraph 3 in response to your suggestions. Hopefully it reads a bit more accurately (and smoothly!) now. Thanks again! – Alex Wertheim Oct 30 '14 at 17:51
• A good, generic way of doing this. You can generalize this to higher degrees by building a list of irreducibles as you go. Not unlike the sieve of Eratosthenes. – Jyrki Lahtonen Oct 30 '14 at 18:36
• @TheD3ac: I don't believe your edits change anything about my answer. As far as how to compute irreducible polynomials of degree two in $\mathbb{Z}_{2}[x]$, note that any reducible polynomial of degree $2$ must be divisible by a linear polynomial in $\mathbb{Z}_{2}[x]$, hence must have a root in $\mathbb{Z}_{2}[x]$. The irreducibles of degree $2$ in $\mathbb{Z}_{2}[x]$ are therefore the degree $2$ polynomials with no roots in $\mathbb{Z}_{2}$. Hence, generate a list of the four possible degree $2$ polynomials, then plug in $0$ and $1$ to see if either is a root. – Alex Wertheim Oct 30 '14 at 20:44

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.

• Wow. This is a beautiful answer, with some really nice techniques I haven't seen before. Thanks for sharing. +1 – Alex Wertheim Oct 30 '14 at 18:29
• Switching to CW, because I just found a dupe target. No more rep for me here. – Jyrki Lahtonen Oct 6 '18 at 15:02

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$.

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}