Polynomial decomposition into irreducible factors

Question

Decompose $x^5 + x + 1$ into irreducible factors in $\mathbb{Z}_2[x]$.

I would like to know how to reason and how to proceed. I am a beginner in this field of mathematics, and I am trying to understand and learn also through examples.

I managed to factor the above polynomial as

$$\left(x^2+x+1\right) \left(x^3-x^2+1\right)$$

Now $x^2+x+1$ is an irreducible quadratic, I think.

How shall I proceed?

Also if you know some notes about this topic, I would be happy and grateful if you linked them here!

Answer 1

It looks like you've already found the factorization, but I'll post a few words on that anyway. It is not overly difficult to brute-force a factorization in small finite fields if the degree of the polynomial to be factored is sufficiently small. This is because there are few monic irreducible polynomials of small degree to be had in these fields (listing such quadratics and maybe even cubics for $\mathbb{Z}_2$ and $\mathbb{Z}_3$ is a good exercise$^\dagger$). Once you have a list of possible divisors, you can just test them one-by-one with polynomial long division.

Since you've found the factorization already, all that's left is to verify the irreducibility of the polynomials in your factorization. This is the easy part: if a polynomial $f$ over a field $F$ is such that $\deg(f) \leq 3$, then $f$ is irreducible $\iff f$ has no roots in $F$ (prove this for yourself: also a good exercise$^\ddagger$). This is super easy for you to check since $\mathbb{Z}_2$ has only $2$ elements.

Of course, if you were factoring, say, a degree $6$ polynomial and got it into a quadratic and a quartic, you'd have to repeat the entire process above on the quartic to verify its irreducibility: the convenient "does it have roots?" irreducibility test only works for quadratics and cubics (very common mistake, don't fall into the trap!).

---

$^\dagger$ Enumerating the monic irreducible polynomials of degree $\leq 5$ over $\mathbb{Z}_2$ is discussed here.

$^\ddagger$ I have a hint here if desired.

Answer 2

Both of your factors are irreducible. A polynomial, over a field $k$, whose degree is $2$ or $3$ is irreducible if and only if it has no roots in $k$. That's clearly the case here.

Answer 3

I’m glad to see that you recognize the importance of working examples in this field. You may find the following useful, or at the very least, interesting:

1. Over the field $\Bbb F_p$ with $p$ elements, the degree-$n$ extension $\Bbb F_{p^n}$ consists exactly of the roots of $X^{p^n}-X$. These roots are partitioned into subsets corresponding to the various $\Bbb F_p$-irreducible factors of $X^{p^n}-X$. The only degrees of such factors are the divisors $d$ of $n$. Accordingly, we have $$ X^{p^n}-X=\prod_ff(X)\,, $$ where the index $f$ runs through the monic $\Bbb F_p$-irreducible polynomials of degree dividing $n$.

2. As a result, if $N(d)$ is the number of monic irreducible polynomials over $\Bbb F_p$ of degree $d$, we have $$ p^n=\sum_{d|n}dN(d)\,. $$

3. Using Möbius Inversion we get $$ N(n)=\frac1n\sum_{d|n}\mu(d)p^{n/d}\,. $$ For instance, to count irreducibles over the field with two elements, there are two linears, one quadratic, two cubics, three quartics, six quintics, nine sextics, etc. Actually finding them is another story.