## Find the irreducible polynomials of degree 1, 2, and 4 over ZZ/(2)

Find all the irreducible polynomials of degree 1, 2, or 4 over $\mathbb{F}_2$, and verify that their product is $x^{16}-x$.

Note that there are $2^k$ (monic) polynomials of degree $k$, as each non-leading coefficient can be either 0 or 1.

The polynomials of degree 1, $p_1(x) = x$ and $p_2(x) = x+1$, are both irreducible.

There are 4 polynomials of degree 2, one of which is irreducible.

1. $x^2 = xx$ is reducible
2. $x^2+1 = (x+1)^2$ is reducible
3. $x^2+x = x(x+1)$ is reducible
4. $p_3(x) = x^2+x+1$ has no roots, and so is irreducible.

Before we address the degree 4 polynomials, we prove a lemma.

Lemma 1: If $p(x)$ is a degree 4 polynomial over $\mathbb{F}_2$ with constant term 1 and $p$ factors as a product of quadratics, then the linear and cubic terms of $p$ are equal. Proof: We have (as we assume) $p(x) = (x^2+ax+b)(x^2+cx+d)$ $= x^4 + (a+c)x^3 + (b+d+ac)x^2 + (ad+bc)x+bd$. Now $bd = 1$, so that $b = d = 1$. So $p(x) = x^4 + (a+c)x^3 + acx^2 + (a+c)x + 1$, as desired. $\square$

Lemma 2: $\Phi_5(x) = x^4+x^3+x^2+x+1$ is irreducible over $\mathbb{F}_2$. Proof: Clearly this has no roots. By Lemma 1, if $\Phi_5(x)$ factors into two quadratics, then the factors’ linear terms, $a$ and $c$, satisfy $a+c=ac=1$, which is impossible over $\mathbb{F}_2$. $\square$

There are 16 polynomials of degree 4.

1. $x^4 = xx^3$ is reducible
2. $x^4+1 = (x^2+1)^2$ is reducible
3. $x^4+x = x(x^3+1)$ is reducible
4. $x^4+x^2 = x^2(x^2+1)$ is reducible
5. $x^4+x^3 = x^3(x+1)$ is reducible
6. $p_4(x) = x^4+x+1$ clearly has no roots, and by the lemma, has no quadratic factors. So $p_4$ is irreducible.
7. $x^4+x^2+1 = (x^2+x+1)^2$ is reducible
8. $p_5(x) = x^4+x^3+1$ clearly has no roots, and by Lemma 1, has no quadratic factors. So $p_5$ is irreducible.
9. $x^4+x^2+x = x(x^3+x+1)$ is reducible
10. $x^4+x^3+x = x(x^3+x^2+1)$ is reducible
11. $x^4+x^3+x^2 = x^2(x^2+x+1)$ is reducible
12. $x^4+x^2+x+1$ has 1 as a root, so is reducible
13. $x^4+x^3+x^2+1 = (x+1)(x^3+1)$ is reducible
14. $x^4+x^3+x^2+1$ has 1 as a root, so is reducible
15. $x^4+x^3+x^2+x = x(x^3+x^2+x+1)$ is reducible
16. $p_6(x) = x^4+x^3+x^2+x+1 = \Phi_5(x)$ is irreducible

So there are six irreducible polynomials of degree 1, 2, or 4 over $\mathbb{F}_2$:

1. $p_1(x) = x$
2. $p_2(x) = x+1$
3. $p_3(x) = x^2+x+1$
4. $p_4(x) = x^4+x+1$
5. $p_5(x) = x^4+x^3+1$
6. $p_6(x) = x^4+x^3+x^2+x+1$

It is easy (if tedious) to verify that the product of these polynomials is $x^{16}-x$. (WolframAlpha agrees.)