# Questions concerning method of finding irreducible polynomials in F_2[X].

In our homework, we are supposed to find all the irreducible polynomials of $$\mathbb F_2[X]$$ with degree $$\leq 4$$. Ok, I know that there are at least two helpful threads dealing with this question: Find all irreducible monic polynomials in $\mathbb{Z}/(2)[x]$ with degree equal or less than 5

Find all irreducible polynomials of degrees 1,2 and 4 over $\mathbb{F_2}$.

(1) According to the first link: "A polynomial of degree $$2$$ or $$3$$ is irreducible if and only if does not have linear factors."

Why? Let's consider $$X^2+X=X(X+1)$$. $$X^2+X$$ is not a unit, and neither are $$X$$ or $$X+1$$, as I see it. So why then isn't $$X^2+X$$ irreducible? [Let $$R$$ be a commutative ring. Then $$r\in R$$ is called irreducible if $$r\ne 0, r\notin R^{\star}$$ and for every decomposition $$r =ab\Rightarrow a\in R^{\star} \vee b\in R^{\star}$$.]

Kind regards, MathIsFun

• If you are really supposed to find all the irreducible polynomials over the field of two elements, you have a long road ahead of you, as there are infinitely many, and no simple pattern. What are you really supposed to do? Also, you write that you have two questions, but your labeling of your "questions" begins and ends with (1). $1\ne2$. Dec 9 '19 at 9:41
• $X^2+X$ can be "decomposed" into two linear factors, namely $X$ and $X+1$. Both are nonzero and not units. Dec 9 '19 at 10:00

Your reasoning already shows that $$X^2+X$$ is not irreducible: Irreducibility means that there are no factorizations $$r=ab$$ with both $$a$$ and $$b$$ a non-unit. As you already stated, neither $$X$$ nor $$X+1$$ are units, so their product is reducible.

In general: Given a polynomial $$f\in\mathbb{F}_2[X]$$ of degree $$2$$ or $$3$$. Any decomposition into factors $$f=ab$$ has to satisfy $$\deg(f)=\deg(a)+\deg(b)$$. Suppose $$\deg(a)\leq\deg(b)$$, then we have two cases:

1)$$\deg(a)=0$$, but then $$a\in\mathbb{F}_2^\ast$$ and hence $$a$$ is a unit

2)$$\deg(a)=1, \deg(b)=1,2$$: Both factors are non-units, hence $$f$$ is reducible

So, $$f$$ is irreducible if and only if it does not factor a linear factor. Note that this reasoning works only for polynomial rings over fields and for polynomials of degree $$\leq 3$$.

• Thanks for the answer so far! Okay, $f$ irreducible iff it doesn't factor a linear factor. But why then does it suffice (as it says in the accepted answer of the second link to which I referred) to show that $p(0) = p(1) = 1$? Take $p(X) = X$ for instance. Clearly, $p$ factors a linear factor (i.e., $X$ itself), but $p(0) = 0\ne 1$!? I guess my reasoning is incorrect at some point ... Dec 10 '19 at 20:34
• (I assume you are refering to the non-accepted answer in your second link) This argument works just in the particular case of $\deg(f)=2,3$: Over a field $F$, any linear polynomial is irreducible (consider again the degrees of possible factorizations and note $F^\ast=F\setminus\lbrace 0\rbrace$), so you don't need a criterion for irreducibility there. Since the polynomial ring over a field is eulidean, you can use polynomial division to show that $p(a)=0$ iff $p(X)$ factors $(X-a)$, so checking for roots is the same as checking for linear factors.
– user149890
Dec 11 '19 at 11:58