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

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

Attempt: Suppose $f(x) = x^4 + a_3x^3 + a_2x^2 + a_1x + a_0 \in \mathbb{F_2}[x]$. Then since $\mathbb{F_2} =${$0,1$}, then we have either $0$ or $1$ for each $a_i$. Then we have two choices for the $4$ coefficients, hence there are 16 polynomials of degree $4$ in $\mathbb{F_2}[x]$.

Recall $f(x)$ is irreducible if and only if it has not roots. Then

$f_1 = x$ is irreducible because it has not roots

$f_2 = x + 1$ is also another irreducible polynomial.

$f_3 = x^4 + x^2 + x = x ( x^3 + x + 1)$ is reducible.

$f_4 = x^4 = x^3* x$ is reducible

$f_5 = x^4 + x + 1$

Can someone please help me? Is there a way I can save time in finding the irreducible polynomials, other than just trying to come up with polynomials. Any better approach or hint would really help! Thank you !

• *"Recall $f(x)$ is irreducible if and only if it has not roots." This is false; the polynomial $x^4+x^2+1$ is reducible but as no roots. – Servaes Dec 7 '15 at 2:56
• "$f(x)$ is irreducible if and only if it has no roots" - not true. For example $(x^2+x+1)^2$ has no roots but is reducible. – David Dec 7 '15 at 2:56
• Degree $1$, every polynomial is irreducible, there are two. Degree $2$, irreducible iff it has no roots, easy, only $x^2+x+1$. Degree $4$ is tougher, a polynomial can be reducible but have no roots. – André Nicolas Dec 7 '15 at 2:57
• Enlisting and checking gives 3 polynomials of degree 4. However, I'm also interested in a quick way as OP has asked. – Shailesh Dec 7 '15 at 2:59

## 2 Answers

Degree $1$, clearly $x$ and $x+1$.

Degree $2$, notice the last coefficient must be one, so there are only two options, $x^2+x+1$ and $x^2+1$. Clearly only $x^2+x+1$ is irreducible.

Degree $4$. There are $8$ polynomials to consider, again, because the last coefficient is $1$, now notice a polynomial is divisible by $x+1$ if and only if the sum of its coefficients is even. So the only polynomials without factors of degree $1$ are four:

$x^4+x^3+x^2+x+1$

$x^4+x^3+1$

$x^4+x^2+1$

$x^4+x+1$.

Of course, we are missing the possibility it is the product of two irreducibles of degree $2$, but the only combination is $(x^2+x+1)(x^2+x+1)=x^4+x^2+1$.

Hence the irreducible ones are:

$x^4+x^3+x^2+x+1,x^4+x^3+1,x^4+x+1$

• So we can say $f = x^4 + x + 1$ is irreducible because it has not quadratic factors. In general not all polynomials of degree 4 will be reducible $x^4 + x^2 + x + 1$ is reducible because it has one root . – Mahidevran Dec 7 '15 at 3:23
• Yeah, it is divisible by $x+1$ (in other words $1$ is a root). – Jorge Fernández Hidalgo Dec 7 '15 at 3:38
• Just something to help others reading this answer who might have been initially confused as I was: "a polynomial is divisible by $x+1$ if and only if the sum of its coefficients is even" this comes from the Remainder Theorem since in $\mathbb{F}_2$ anything even mods to zero. – Raj Apr 8 at 18:28

$f_1$ is irreducible because $f_1 (0)=a0\equiv_2 0$. We cannot have an irreducible polynomial of degree one because we must have that $a=1$(otherwise it is constant), and $ax+1$ has $1$ as a solution. If our constant term is zero, then we have the root $0$ as described above.

Now for polynomials of degree 2, we want to determine when $ax^2+bx+c\equiv_2 0$. We plug in both $0$ and $1$ to obtain that $c$ is not equivalent to $0$ mod $2$ (so it must be $1$), and that $a+b+1$ is also not equivalent to $0$ mod $2$. This tells us that polynomial must be of the form $x^2+x+1$, because if either $a$ or $b$ were $0$ then it would have a solution of $x=1$.

Perform this same reasoning process for 4th degree polyomials.

• Except fourth degree can factor into irreducible quadratics, so eliminate that possibility first. – Macavity Dec 7 '15 at 3:02