Reduction modulo p test for irreducibility

Statement

Let $f \in \mathbb{Z}[x]$ be a monic polynomial and let $p$ be a prime number. Let $\bar{f} \in \mathbb{F}_p[x]$ be the polynomial whose coefficients are those of $f$ modulo $p$. If $\bar{f}$ is irreducible in $\mathbb{F}_p[x]$, then $f$ is irreducible in $\mathbb{Z}[x]$ and in $\mathbb{Q}[x]$.

Remarks

The proof: a factorisation $f = g h$ into monic factors of positive degree gives $\bar{f} = \bar{g} \bar{h}$, with $\deg \bar{g} = \deg g$ and $\deg \bar{h} = \deg h$. Irreducibility in $\mathbb{Q}[x]$ then follows by Gauss's lemma. The converse is false: $x^4 + 1$ is irreducible over $\mathbb{Q}$, but it is reducible modulo every prime. Example: $x^3 + x + 1$ has no root in $\mathbb{F}_2$, so it is irreducible over $\mathbb{F}_2$, and so over $\mathbb{Q}$.

Explanations

L1 human

A factorisation over the integers stays a factorisation after reduction modulo $p$. So if the reduced polynomial does not factor, the original one does not factor either. Over a small finite field, you can check irreducibility by a finite search.