Find All Irreducible Polynomials of Degrees 2 and 3 in F₂[x]

The notation $\mathbb{F}_2[x]$ means polynomials whose coefficients come from the two-element field $\mathbb{F}_2 = \{0,1\}$. In this field, addition and multiplication are performed modulo 2, so $1+1=0$. The complete list of irreducibles of the requested degrees is short: there is one of degree 2 and two of degree 3.

Why checking roots is enough

A nonconstant polynomial is irreducible over a field if it cannot be written as a product of two polynomials of smaller positive degree over that field. A reducible quadratic must factor into two linear factors, and a reducible cubic must factor into a linear factor and a quadratic factor. In either case, it has a linear factor, which is equivalent to having a root in the field.

There are only two possible roots to check in $\mathbb{F}_2$: 0 and 1. Thus a quadratic or cubic over $\mathbb{F}_2$ is irreducible exactly when its values at both 0 and 1 are nonzero. The only nonzero value in this field is 1.

Also, every polynomial in this list is monic: its leading coefficient must be the only nonzero field element, 1.

The irreducible quadratic

The general monic quadratic is $x^2+ax+b$, where $a,b\in\{0,1\}$. Checking the four possibilities gives:

Polynomial	Root or factorization in $\mathbb{F}_2[x]$
$x^2$	$x\cdot x$
$x^2+1$	$(x+1)^2$
$x^2+x$	$x(x+1)$
$x^2+x+1$	No root in $\mathbb{F}_2$

For the last polynomial, the root checks are

$$\begin{aligned} f(0)&=1,\\ f(1)&=1+1+1=1 \quad\text{in }\mathbb{F}_2. \end{aligned}$$

It has no root, so it is irreducible. Therefore the only irreducible quadratic is

$x^2+x+1.$

The irreducible cubics

Write a general monic cubic as

$f(x)=x^3+ax^2+bx+c,\qquad a,b,c\in\{0,1\}.$

If $c=0$, then $f(0)=0$, so the polynomial is divisible by $x$ and is reducible. For a possible irreducible cubic, we must have $c=1$. Now evaluate at 1:

$f(1)=1+a+b+1=a+b,$

where the arithmetic is in $\mathbb{F}_2$. To avoid a root at 1, we need $a+b=1$. There are exactly two choices: $(a,b)=(0,1)$ and $(a,b)=(1,0)$. They give

$x^3+x+1 \quad\text{and}\quad x^3+x^2+1.$

For each one, substituting 0 gives 1, and substituting 1 also gives 1. Neither has a root in $\mathbb{F}_2$, so both are irreducible.

For comparison, the two remaining cubics with constant term 1 have $a=b$, hence a root at 1. In fact, $x^3+1=(x+1)(x^2+x+1)$ and $x^3+x^2+x+1=(x+1)^3$ in this field. Together with the four cubics having constant term 0, this accounts for all eight monic cubics.

Complete list

The answer is

• Degree 2: $x^2+x+1$.
• Degree 3: $x^3+x+1$ and $x^3+x^2+1$.

As a quick count check, the standard formula for the number of monic irreducible polynomials of degree $n$ over a field with $q$ elements gives 1 for $q=2,n=2$ and 2 for $q=2,n=3$, matching the direct enumeration.

Common mistakes

• Using ordinary integer arithmetic. In $\mathbb{F}_2$, terms such as $x+x$ cancel because their coefficient is $1+1=0$.
• Checking only the constant term. A nonzero constant term rules out a root at 0, but you must also test 1.
• Looking for factors with integer coefficients. Irreducibility here is specifically over $\mathbb{F}_2$; coefficients and factorizations are taken in that field.
• Assuming “no root” always proves irreducible. It does for degree 2 and 3 because any proper factorization of either degree must include a linear factor. For degree 4 or higher, a polynomial can factor into higher-degree pieces without having a root in the base field.