Find all irreducible polynomials of degrees $2$ and $3$ in $\Bbb{Z}_{2}[x]$.

Find all irreducible polynomials of degrees $2$ and $3$ in $\Bbb{Z}_{2}[x]$.

A polynomial $p(x)$ of degree $2$ or $3$ is irreducible if and only if it does not have linear factors. Therefore, it suffices to show that $p(0) = p(1) = 1$. This quickly tells us that $x^2 + x + 1$ is the only irreducible polynomial of degree $2$. This also tells us that $x^3 + x^2 + 1$ and $x^3 + x + 1$ are the only irreducible polynomials of degree $3$.

The part I don't understand is "it suffices to show $p(0)=p(1)=1$". Could someone please explain what this means and how this finds the irreducible polynomials?

• If you are looking for irreducible polynomial of degree 3 or 2 in a fieldYou just have to show it has no zeros. – Sorfosh Apr 8 '18 at 0:53

Transform the "if and only if" statement as follows.

A polynomial $p(x)$ of degree $2$ or $3$ is reducible if and only if it has linear factor.

By the factor theorem,

$p(x)$ has linear factor iff $p(0) = 0$ or $p(1) = 0$.

Take the negation on both sides.

$p(x)$ has no linear factor iff $p(0) \ne 0$ and $p(1) \ne 0$.

Since we are in $\Bbb{Z}_2$, the RHS can be simply written as follows.

$p(x)$ has no linear factor iff $p(0) = p(1) = 1$.

In $\Bbb{Z}_2[X]$,

• $p(0) = 1$ iff the constant term is $1$.
• $p(1) = 1$ iff the polynomial contains odd number of terms.

This helps us to select the irreducible polynomials of degree $\le 3$ by eliminating those with even number of terms and/or no constant term.

• Thank you for giving a very clear answer, I understand now... the $0$ and $1$ are elements in $\Bbb{Z}_{2}$. But how does this theorem find the irreducible polynomials? – numericalorange Apr 8 '18 at 1:02
• @numericalorange I've edited my answer to explain how to use $p(0)$ and $p(1)$ to check irreducibility of $p$. The Factor Theorem allows us to find linear factors of a polynomial by substituting values into the indeterminate. – GNUSupporter 8964民主女神 地下教會 Apr 8 '18 at 1:08
• Thanks! Very interesting read! – numericalorange Apr 8 '18 at 1:17