Polynomial rings and irreducibility tests

In one sentence

$K[x]$ over a field is Euclidean and so as well behaved as $\mathbb{Z}$, and every irreducibility test is a one-way implication whose failure proves nothing.

Why the exam asks it

Because "is this polynomial irreducible" is a question with several tests and no algorithm, so the skill is choosing the right one — and because "no roots" is an equivalence for degree $2$ and $3$ and false from degree $4$, which is exactly the sort of boundary an option can sit on.

The idea

For $K$ a field, $K[x]$ has a division algorithm, hence is Euclidean, hence a PID and a UFD. So irreducible elements generate maximal ideals, gcds exist and satisfy Bézout, and factorisation is unique.

Over a domain rather than a field, a polynomial of degree $n$ has at most $n$ roots. That fails without the domain hypothesis: $x^2 - 1$ has four roots in $\mathbb{Z}/8$, namely $1, 3, 5, 7$.

Roots and degree

$a$ is a root $\iff (x-a) \mid f$. Hence:

• Degree $2$ or $3$: irreducible $\iff$ no root in $K$. A factorisation must produce a linear factor.
• Degree $\ge 4$: no root proves nothing. $x^4 + 4$ has no rational root and factors as $(x^2-2x+2)(x^2+2x+2)$ — the Sophie Germain identity. So does $(x^2+1)^2$.

The tests over $\mathbb{Q}$

Rational root theorem. A root $p/q$ in lowest terms has $p \mid a_0$ and $q \mid a_n$. Finite list, quick to check, and it settles degrees $2$ and $3$ completely.

Gauss's lemma. A primitive polynomial in $\mathbb{Z}[x]$ is irreducible over $\mathbb{Z}$ $\iff$ irreducible over $\mathbb{Q}$. So the question can always be moved to $\mathbb{Z}$, which is what makes the next two tests legitimate.

Eisenstein at $p$. If $p \nmid a_n$, $p \mid a_i$ for all $i < n$, and $p^2 \nmid a_0$, then $f$ is irreducible over $\mathbb{Q}$.

Eisenstein failing says nothing, and the standard rescue is a substitution. The cyclotomic polynomial $\Phi_5 = x^4+x^3+x^2+x+1$ admits no Eisenstein prime; but

$$\Phi_5(x+1) = x^4 + 5x^3 + 10x^2 + 10x + 5$$

is Eisenstein at $5$. Since $x \mapsto x+1$ is a ring automorphism of $\mathbb{Q}[x]$, irreducibility transfers back. Trying $x+1$ before concluding anything is the habit worth forming.

Reduction mod $p$. If $f$ is monic and $\bar f$ is irreducible in $\mathbb{F}_p[x]$ of the same degree, then $f$ is irreducible over $\mathbb{Q}$.

This runs one way only, and the counterexample is worth carrying: $x^4+1$ is irreducible over $\mathbb{Q}$ and reducible modulo every prime. So no amount of reduction will ever prove it irreducible, and reducibility mod $p$ never implies reducibility over $\mathbb{Q}$.

Finite fields

$\mathbb{F}_p[x]/(f)$ is a field with $p^{\deg f}$ elements exactly when $f$ is irreducible. That is the standard construction of $\mathbb{F}_{p^n}$, and it is why counting irreducible polynomials of each degree over $\mathbb{F}_p$ is a recurring question.

Over $\mathbb{F}_p$, $x^p - x$ factors as the product of $(x-a)$ over all $a \in \mathbb{F}_p$ — every element is a root, by Fermat.

Where intuition breaks

"No roots, so irreducible." Only for degree $2$ and $3$. $x^4+4$ and $(x^2+1)^2$ are the standard degree-$4$ refutations.

"Eisenstein fails, so reducible." Eisenstein is sufficient, never necessary. Try a shift before concluding anything.

"Reducible mod $p$, so reducible over $\mathbb{Q}$." $x^4+1$ factors modulo every prime and is irreducible over $\mathbb{Q}$. The implication runs the other way: irreducible mod $p$ $\Rightarrow$ irreducible over $\mathbb{Q}$.

"Irreducible over $\mathbb{Q}$, so irreducible mod $p$." Same example. $x^2+x+1$ is irreducible over $\mathbb{Q}$ and equals $(x-1)^2$ mod $3$.

"A degree-$n$ polynomial has at most $n$ roots." Over a domain. In $\mathbb{Z}/8$, $x^2-1$ has four roots.

"$\mathbb{Z}[x]$ has a division algorithm." Only when the leading coefficient is a unit. $x$ divided by $2$ has no quotient in $\mathbb{Z}[x]$, which is why $\mathbb{Z}[x]$ is not Euclidean.

"Irreducible over $\mathbb{Z}$ and over $\mathbb{Q}$ are different questions." For primitive polynomials, Gauss says they are the same. The distinction only matters for content: $2x$ is irreducible over $\mathbb{Q}$ and factors as $2 \cdot x$ over $\mathbb{Z}$.

The exam's angle

1. Check the degree first. At $2$ or $3$, hunt for a rational root and you are done either way.
2. At degree $\ge 4$, try Eisenstein, then Eisenstein after $x \to x+1$, then reduction mod a small prime.
3. Use reduction to prove irreducibility, never reducibility.
4. For explicit factorisations, look for identities — $x^4+4$ and $x^4+4y^4$ are Sophie Germain, and $x^n - 1$ splits into cyclotomics.
5. Over $\mathbb{F}_p$, count. Questions about $\mathbb{F}_{p^n}$ usually reduce to counting monic irreducibles of a given degree.

The night before

• $K[x]$ over a field: Euclidean, PID, UFD. $\mathbb{Z}[x]$ is none of the first two.
• Degree $\le n$ has $\le n$ roots over a domain. $x^2-1$ has four roots in $\mathbb{Z}/8$.
• Degree $2$ or $3$: irreducible $\iff$ no root. Degree $\ge 4$: no root proves nothing — $x^4+4 = (x^2-2x+2)(x^2+2x+2)$.
• Rational root: $p \mid a_0$, $q \mid a_n$.
• Gauss: primitive in $\mathbb{Z}[x]$ — irreducible over $\mathbb{Z}$ $\iff$ over $\mathbb{Q}$.
• Eisenstein is sufficient only; try $x \to x+1$. $\Phi_5(x+1)$ is Eisenstein at $5$.
• Reduction mod $p$ proves irreducibility, never reducibility. $x^4+1$ is irreducible over $\mathbb{Q}$ and reducible mod every prime.
• $\mathbb{F}_p[x]/(f)$ is a field of $p^{\deg f}$ elements $\iff f$ irreducible.