Irreducible polynomials play the role of primes in $F[x]$, and they are exactly what we need to build fields ($F[x]/(f)$ is a field when $f$ is irreducible, by the maximal ideal theorem). For small degrees there is a quick test.
Definition. A polynomial $f \in F[x]$ of degree at least $1$ is irreducible over $F$ if it is not a product of two polynomials of lower degree. Irreducibility depends on the field: $x^{2} - 2$ is irreducible over $\mathbb{Q}$ but equals $(x - \sqrt{2})(x + \sqrt{2})$ over $\mathbb{R}$.
Why it works
Proof. If it factors, the degrees of the factors add to $2$ or $3$, so one factor has degree $1$, say $a(x - c)$, and then $c$ is a root. Conversely, a root $c$ gives the factor $x - c$. $\square$ For degree $4$ and up this fails: a product of two irreducible quadratics has no roots.
Over $\mathbb{Z}_{p}$ you can test every element. There are $\frac{p^{2} - p}{2}$ monic irreducible quadratics over $\mathbb{Z}_{p}$: of the $p^{2}$ monic quadratics, the reducible ones are $(x - a)(x - b)$, and there are $p$ with $a = b$ plus $\binom{p}{2}$ with $a \ne b$.
Worked example: The same polynomial, two fields
- Over $\mathbb{Z}_{3}$: $0 + 1 = 1$, $1 + 1 = 2$, $4 + 1 = 5 \equiv 2$. No root: irreducible.
- Over $\mathbb{Z}_{5}$: $2^{2} + 1 = 5 \equiv 0$. So $x^{2} + 1 = (x - 2)(x - 3) = (x + 3)(x + 2)$: reducible.
Answer: Irreducible over $\mathbb{Z}_{3}$, reducible over $\mathbb{Z}_{5}$.
Worked example: Irreducibles over $\mathbb{Z}_{2}$
- A root in $\mathbb{Z}_{2}$ is $0$ or $1$. No root at $0$ means constant term $1$; no root at $1$ means an odd number of nonzero terms.
- Degree 2: $x^{2} + x + 1$ only ($x^{2} + 1 = (x + 1)^{2}$).
- Degree 3: $x^{3} + x + 1$ and $x^{3} + x^{2} + 1$.
Answer: $x^{2} + x + 1$; $x^{3} + x + 1$, $x^{3} + x^{2} + 1$.
Worked example: Degree 4 needs more
- Check the only irreducible quadratic: $(x^{2} + x + 1)^{2} = x^{4} + 2x^{3} + 3x^{2} + 2x + 1 = x^{4} + x^{2} + 1$ (mod 2).
Answer: No: it is $(x^{2} + x + 1)^{2}$.
Common mistake
Key idea