Irreducible Polynomials

Irreducibles Are the Primes of a Polynomial Ring

Recall from Polynomial Rings that a polynomial $p(x)\in R[x]$ is irreducible if $p(x)$ is neither the zero polynomial nor a unit, and whenever $p(x)=f(x)g(x)$ we are forced to have $f(x)\in R[x{]}^{\ast }$ or $g(x)\in R[x{]}^{\ast }$. Over a field $F$ the units of $F[x]$ are exactly the nonzero constants, so irreducibility says that the only factorisations available are the trivial ones where you peel a constant off the front.

Now compare that with the definition of a prime from Divisibility and Primes: an integer $p>1$ whose only divisors are $\pm 1$ and $\pm p$, i.e. an integer whose only factorisations are the ones where you peel a unit of $\mathbb{Z}$ off the front. The two definitions are the same sentence with the ring swapped out, and this whole lecture is the payoff: essentially every result about primes has a polynomial twin.

Basically, "irreducible" is just the word "prime" wearing a different hat, and the job for this lecture is the polynomial version of a primality test: given $f(x)$, decide whether it factors. Everything we build below — degree bounds, root tests, reduction mod $p$ — is a translation of something we already did to integers.

There is one genuinely new wrinkle, and it is the thing students get wrong most often. An integer is prime or not, full stop; but a polynomial can be irreducible in one ring and split apart in a bigger one. For instance $x^2-2$ has no factorisation at all in $\mathbb{Q}[x]$, yet $x^2-2=(x-\sqrt{2})(x+\sqrt{2})$ in $\mathbb{R}[x]$. Irreducibility is never a property of a polynomial on its own; it is a property of the polynomial together with the ring its coefficients are allowed to live in, so always say "irreducible in $\mathbb{Q}[x]$" and never just "irreducible".

Roots and the Factor Theorem

The single most useful tool for spotting a factor is the observation that linear factors and roots are the same information. It falls straight out of the Division Theorem.

Proof. The divisor $x-a$ is monic, so its leading coefficient $1$ is a unit of $R$; hence the Division Theorem applies over any ring $R$ (this is the Fact from Polynomial Rings). It gives unique $q(x),r(x)\in R[x]$ with

$$f(x)=q(x)(x-a)+r(x),\mathrm{deg}(r(x))<\mathrm{deg}(x-a)=1.$$

A polynomial of degree less than $1$ is either the zero polynomial or a constant, so $r(x)=r$ for some fixed $r\in R$. Now evaluate both sides at $x=a$:

$$\begin{array}{rl}f(a)& =q(a)(a-a)+r\\ & =q(a)\cdot 0+r\\ & =r.\end{array}$$

So the remainder is the constant $f(a)$. $■$

Basically, dividing by $x-a$ and substituting $x=a$ are two ways of doing the same computation; the $(x-a)q(x)$ part is annihilated by the substitution and only the remainder survives. Setting the remainder to zero immediately gives the result we actually use.

Example. Find the remainder when $f(x)=x^4+3x^2-2x+5$ is divided by $x-2$ in $\mathbb{Q}[x]$, and decide whether $x-2$ is a factor.
By the Remainder Theorem the remainder is just $f(2)$;

$$\begin{array}{rl}f(2)& =2^4+3(2^2)-2(2)+5\\ & =16+12-4+5\\ & =29.\end{array}$$

Therefore the remainder is $29$, and since $29\ne 0$ we have $(x-2)\nmid f(x)$. Notice how much cheaper this was than actually running the long division; whenever the divisor is linear, evaluate instead of dividing.

Example. Find all $a\in {\mathbb{Z}}_5$ such that $(x-a)\mid x^3+x+1$ in ${\mathbb{Z}}_5[x]$.
By the Factor Theorem this is asking for the roots of $f(x)=x^3+x+1$ in ${\mathbb{Z}}_5$, and since ${\mathbb{Z}}_5$ is finite we can simply substitute every element:

$$\begin{array}{rl}f(0)& =0+0+1=1,\\ f(1)& =1+1+1=3,\\ f(2)& =8+2+1=11=1,\\ f(3)& =27+3+1=31=1,\\ f(4)& =64+4+1=69=4\text{ in }{\mathbb{Z}}_5.\end{array}$$

None of the five values is $0$, so $f(x)$ has no roots in ${\mathbb{Z}}_5$. Therefore no linear polynomial $x-a$ divides $x^3+x+1$ in ${\mathbb{Z}}_5[x]$. This "just try everything" move is only available because the ring is finite, and it is the reason irreducibility questions over ${\mathbb{Z}}_n$ are so much easier than over $\mathbb{Q}$.

How Many Roots a Polynomial Can Have

Over $\mathbb{Z}$ a positive integer only has finitely many divisors, and the polynomial version of that bound is a statement about roots.

Proof. We induct on $n$, using the Factor Theorem at every step. Throughout we use the fact that $R$ has no zero divisors, i.e. that $uv=0$ forces $u=0$ or $v=0$ (see the warning below).

Base case ($n=1$). Let $f(x)=a_{1}x+a_0$ with $a_1\ne 0$, and suppose $b$ and $c$ are both roots. Then

$$\begin{array}{rl}{a}_{1}b+a_0& =0=a_{1}c+a_0,\\ a_{1}b& =a_{1}c,\\ a_1(b-c)& =0,\end{array}$$

and since $a_1\ne 0$ we must have $b-c=0$, i.e. $b=c$. So a degree $1$ polynomial has at most one root.

Inductive step. Suppose every polynomial of degree $n-1$ has at most $n-1$ roots, and let $\mathrm{deg}(f(x))=n$. If $f(x)$ has no roots at all then it certainly has at most $n$ of them and we are done. Otherwise pick a root $a$; by the Factor Theorem,

$$f(x)=(x-a)g(x)\text{for some }g(x)\in R[x],$$

and comparing degrees gives $\mathrm{deg}(g(x))=n-1$. Now let $b$ be any root of $f(x)$ with $b\ne a$. Then

$$\begin{array}{rl}0& =f(b)\\ & =(b-a)g(b),\end{array}$$

and $b-a\ne 0$, so we are forced into $g(b)=0$. In other words every root of $f(x)$ other than $a$ is a root of $g(x)$, and by the inductive hypothesis there are at most $n-1$ of those. Hence $f(x)$ has at most $1+(n-1)=n$ roots. $■$

Basically, each root you find lets you strip off one linear factor, and the degree only has $n$ layers to give away before it runs out.

The proof used "$uv=0\Rightarrow u=0$ or $v=0$" twice, and that is exactly the axiom a general ring does not have. A ring with no zero divisors is called an integral domain; $\mathbb{Z}$, $\mathbb{Q}$, $\mathbb{R}$, $\mathbb{C}$ and ${\mathbb{Z}}_p$ for prime $p$ are all integral domains, and those are the only rings this course ever applies Theorem 7.16 to. If you drop that assumption the theorem is flat out false. The standard counterexample is $x^2-1$ over ${\mathbb{Z}}_8$:

$$\begin{array}{rl}{1}^2-1& =0,\\ 3^2-1& =8=0,\\ 5^2-1& =24=0,\\ 7^2-1& =48=0\text{ in }{\mathbb{Z}}_8,\end{array}$$

so a degree $2$ polynomial has four roots. There is no contradiction with the proof, because $x^2-1=(x-1)(x+1)$ and at $x=3$ we get $2\times 4=8=0$ in ${\mathbb{Z}}_8$ from two nonzero factors; the zero divisors let a product vanish without either bracket vanishing. So before quoting the at-most-$n$-roots theorem, check that your ring has no zero divisors — in practice, that $R$ is a field, or $\mathbb{Z}$, or ${\mathbb{Z}}_p$ with $p$ prime. Recall from Modular Rings and Units that ${\mathbb{Z}}_n$ has zero divisors precisely when $n$ is composite, which is the whole reason we insist on prime moduli in this topic.

Irreducibles over C and R

The complex numbers are the easiest case, because there is nowhere left for a root to hide.

The proof of this is well beyond the course (every proof of it smuggles in some analysis or topology somewhere), so we just quote it. Read the statement as being about non-constant polynomials; a nonzero constant polynomial obviously never takes the value $0$.

Proof (sketch). Induct on $n$. For $n=1$, $f(x)=a_{1}x+a_0$ has the single root $-a_0/a_1$. For the step, Theorem 7.17 hands us a root $a$ of $f(x)$, and the Factor Theorem turns it into $f(x)=(x-a)g(x)$ with $\mathrm{deg}(g(x))=n-1$; by the inductive hypothesis $g(x)$ has exactly $n-1$ roots with multiplicity, and $\mathbb{C}$ has no zero divisors so the roots of $f(x)$ are exactly $a$ together with the roots of $g(x)$. That is $n$ altogether. $■$

Basically, over $\mathbb{C}$ the process of stripping off linear factors never gets stuck; it keeps going until the degree is exhausted, so every complex polynomial splits completely into linear pieces.

Proof. ($\Leftarrow$) Suppose $\mathrm{deg}(f(x))=1$ and $f(x)=g(x)h(x)$. Degrees add over a field, so $\mathrm{deg}(g(x))+\mathrm{deg}(h(x))=1$ and one of the two factors has degree $0$, i.e. is a nonzero constant. Since $\mathbb{C}[x{]}^{\ast }={\mathbb{C}}^{\ast }$, that factor is a unit; so $f(x)$ is irreducible.
($\Rightarrow$) Suppose $f(x)$ is irreducible, so $f(x)$ is not a unit and hence $\mathrm{deg}(f(x))\ge 1$. If $\mathrm{deg}(f(x))=n\ge 2$, then by Theorem 7.17 there is a root $a\in \mathbb{C}$, and by the Factor Theorem

$$f(x)=(x-a)g(x),\mathrm{deg}(g(x))=n-1\ge 1.$$

Neither factor is a constant, so neither is a unit, contradicting irreducibility. Hence $n=1$. $■$

Over $\mathbb{R}$ the story is only slightly longer, because a real polynomial can have complex roots — but those always come in conjugate pairs, and multiplying a pair back together lands you in the reals again.

Proof. Suppose $\mathrm{deg}(f(x))=n\ge 3$; we show $f(x)$ is reducible in $\mathbb{R}[x]$. Regard $f(x)$ as an element of $\mathbb{C}[x]$; by Theorem 7.17 it has a root $z\in \mathbb{C}$.

Case 1: $z\in \mathbb{R}$. Then the Factor Theorem applies inside $\mathbb{R}[x]$ and gives $f(x)=(x-z)g(x)$ with $g(x)\in \mathbb{R}[x]$ and $\mathrm{deg}(g(x))=n-1\ge 2$. Neither factor is a constant, so $f(x)$ is reducible.

Case 2: $z\notin \mathbb{R}$. Write $z=\alpha +\beta i$ with $\alpha ,\beta \in \mathbb{R}$ and $\beta \ne 0$. Writing $f(x)={\sum }_{k=0}^n{a}_k{x}^k$ with every $a_k\in \mathbb{R}$, and using the fact that conjugation respects sums and products while fixing every real number,

$$\begin{array}{rl}f(\bar{z})& =\sum _{k=0}^n{a}_k{\bar{z}}^k\\ & =\sum _{k=0}^n\overline{a_k}\overline{z^k}(\text{since }\overline{a_k}=a_k\text{ as }{a}_k\in \mathbb{R})\\ & =\overline{\sum _{k=0}^n{a}_k{z}^k}\\ & =\overline{f(z)}\\ & =\bar{0}=0,\end{array}$$

so $\bar{z}=\alpha -\beta i$ is also a root, and $\bar{z}\ne z$ because $\beta \ne 0$. Hence $(x-z)$ and $(x-\bar{z})$ are two distinct linear factors of $f(x)$ in $\mathbb{C}[x]$, so their product divides $f(x)$. But that product is

$$\begin{array}{rl}(x-z)(x-\bar{z})& =x^2-(z+\bar{z})x+z\bar{z}\\ & =x^2-2\alpha x+({\alpha }^2+{\beta }^2),\end{array}$$

which has real coefficients. Call it $d(x)$. Dividing $f(x)$ by the monic real polynomial $d(x)$ inside $\mathbb{R}[x]$ gives $f(x)=q(x)d(x)+r(x)$ with $q(x),r(x)\in \mathbb{R}[x]$ and $\mathrm{deg}(r(x))<2$; and since the Division Theorem in $\mathbb{C}[x]$ has a unique answer, which we already know has remainder $0$, we get $r(x)=0$. Hence

$$f(x)=d(x)q(x),q(x)\in \mathbb{R}[x],\mathrm{deg}(q(x))=n-2\ge 1,$$

and again $f(x)$ is reducible. Either way $n\ge 3$ makes $f(x)$ reducible, so an irreducible real polynomial has degree $1$ or $2$. $■$

Basically, real irreducible quadratics are exactly the ones with a conjugate pair of complex roots — the ones with negative discriminant. So the complete factorisation of a real polynomial is a product of linear factors (one per real root) and irreducible quadratics (one per conjugate pair).

Factoring the Same Polynomial in Different Rings

The best way to feel how much the ambient ring matters is to factor one polynomial three times.

Example. Write $x^4-4$ as a product of irreducible polynomials in (a) $\mathbb{Q}[x]$, (b) $\mathbb{R}[x]$, (c) $\mathbb{C}[x]$.
Every case starts from the difference of two squares, $x^4-4=(x^2{)}^2-2^2$:

$$\begin{array}{rl}{x}^4-4& =(x^2-2)(x^2+2).\end{array}$$

(a) In $\mathbb{Q}[x]$ we claim both brackets are already irreducible. Each has degree $2$, so a nontrivial factorisation would have to be (linear)(linear), and by the Factor Theorem a linear factor $x-a$ exists exactly when there is a rational root. Testing the only candidates allowed by the rational root theorem (Theorem 7.25 below), namely $p\mid 2$ and $q\mid 1$ so $x\in \{\pm 1,\pm 2\}$:

$$\begin{array}{rlrl}(\pm 1{)}^2-2& =-1,& (\pm 2{)}^2-2& =2,\\ (\pm 1{)}^2+2& =3,& (\pm 2{)}^2+2& =6,\end{array}$$

none of which is $0$. Therefore, in $\mathbb{Q}[x]$,

$$x^4-4=(x^2-2)(x^2+2).$$

(b) In $\mathbb{R}[x]$ the number $\sqrt{2}$ is now available, so $x^2-2$ splits; but $x^2+2\ge 2>0$ for every real $x$, so it has no real roots and (being quadratic) stays irreducible. Therefore

$$x^4-4=(x-\sqrt{2})(x+\sqrt{2})(x^2+2).$$

(c) In $\mathbb{C}[x]$ Theorem 7.19 tells us in advance that the answer must be a product of four linear factors, and $x^2+2=x^2-(i\sqrt{2}{)}^2$ finishes the job. Therefore

$$x^4-4=(x-\sqrt{2})(x+\sqrt{2})(x-i\sqrt{2})(x+i\sqrt{2}).$$

Notice how each step is the previous factorisation with one more irreducible cracked open; enlarging the ring can only ever break factors further apart, never glue them back together.

Example. Show that $x^2+1$ is irreducible in ${\mathbb{Z}}_3[x]$.
The degree is $2$, so the only possible nontrivial factorisation is into two linear factors, and by the Factor Theorem that happens if and only if $f(x)=x^2+1$ has a root in ${\mathbb{Z}}_3$. Since ${\mathbb{Z}}_3=\{0,1,2\}$ is finite we just check all three:

$$\begin{array}{rl}f(0)& =0+1=1,\\ f(1)& =1+1=2,\\ f(2)& =4+1=5=2\text{ in }{\mathbb{Z}}_3.\end{array}$$

None of these is $0$, so $x^2+1$ has no roots in ${\mathbb{Z}}_3$ and hence no linear factors. Therefore $x^2+1$ is irreducible in ${\mathbb{Z}}_3[x]$. (Contrast this with ${\mathbb{Z}}_5[x]$, where $2^2+1=5=0$, so $x^2+1=(x-2)(x+2)=(x+3)(x+2)$ splits; same polynomial, different ring, opposite answer.)

"No roots" only proves irreducibility for degrees $2$ and $3$. For those degrees any nontrivial factorisation is forced to include a linear factor, which is the same as a root; but from degree $4$ upwards a polynomial can factor into two quadratics without ever taking the value $0$. The cleanest counterexample is the square of the polynomial we just did, over the same ring:

$$\begin{array}{rl}(x^2+1{)}^2& =x^4+2x^2+1,\end{array}$$

whose values at $x=0,1,2$ in ${\mathbb{Z}}_3$ are

$$\begin{array}{rl}0+0+1& =1,\\ 1+2+1& =4=1,\\ 16+8+1& =25=1\text{ in }{\mathbb{Z}}_3,\end{array}$$

so $x^4+2x^2+1$ has no roots in ${\mathbb{Z}}_3$ at all, and yet it is visibly reducible. Never conclude "no roots, therefore irreducible" without first checking that the degree is $2$ or $3$.

Example. Write $x^4-4$ as a product of irreducible polynomials in ${\mathbb{Z}}_3[x]$.
First reduce the coefficients: $-4=-4+6=2$ in ${\mathbb{Z}}_3$, so we are factoring $x^4+2$. The difference-of-squares split from before still works, and we may as well reuse it:

$$\begin{array}{rl}{x}^4-4& =(x^2-2)(x^2+2)\\ & =(x^2+1)(x^2-1)(\text{since }-2=1\text{ and }2=-1\text{ in }{\mathbb{Z}}_3)\\ & =(x^2+1)(x-1)(x+1)\\ & =(x+1)(x+2)(x^2+1)(\text{since }-1=2\text{ in }{\mathbb{Z}}_3).\end{array}$$

The two linear factors are irreducible automatically, and we showed just above that $x^2+1$ is irreducible in ${\mathbb{Z}}_3[x]$. Therefore

$$x^4-4=(x+1)(x+2)(x^2+1)\text{ in }{\mathbb{Z}}_3[x].$$

As a check, expanding gives $x^4+3x^3+3x^2+3x+2$, and reducing mod $3$ leaves $x^4+2=x^4-4$ as required. Notice how the factorisation over $\mathbb{Q}$ survived the reduction: $x^2-2$ became the irreducible $x^2+1$, while $x^2+2$ (irreducible over $\mathbb{Q}$) cracked into $(x-1)(x+1)$. Reducing mod $p$ can break factors that were solid over $\mathbb{Q}$, which is a hint of both the power and the danger of the mod $p$ tests later on.

Irreducibles over Q and Z

Deciding irreducibility over $\mathbb{Q}$ looks nastier than over ${\mathbb{Z}}_p$, because $\mathbb{Q}$ is infinite and you cannot just try everything. The saving grace is that fractions never help you factor.

Proof (sketch). One direction is easy: a factorisation in $\mathbb{Z}[x]$ into two non-constant pieces is also a factorisation in $\mathbb{Q}[x]$. The content is the other direction, and it is due to a result called Gauss's lemma, which states that any $f(x)\in \mathbb{Z}[x]$ whose coefficients have a GCD of $1$ can only be written as a product of polynomials which themselves have coefficients with a GCD of $1$. Given a factorisation over $\mathbb{Q}$, clear all the denominators to get a factorisation over $\mathbb{Z}$ scaled by some integer; Gauss's lemma says the scaling factor has nowhere to hide and must be $\pm 1$, so the $\mathbb{Z}$-factorisation was there all along. $■$

A polynomial in $\mathbb{Z}[x]$ whose coefficients have GCD $1$ is called primitive, and the assumption matters. If we allow a common factor then $\mathbb{Z}$-irreducibility and $\mathbb{Q}$-irreducibility genuinely disagree: $2x^2+2=2(x^2+1)$ is reducible in $\mathbb{Z}[x]$ (because $2$ is not a unit of $\mathbb{Z}$) while it is irreducible in $\mathbb{Q}[x]$ (because $2$ is a unit of $\mathbb{Q}$). From here to the end of the note, every $f(x)\in \mathbb{Z}[x]$ is assumed primitive; if yours is not, divide out the GCD of the coefficients first and test what is left.

Basically, this is the polynomial version of clearing denominators in an equation. Multiplying by the constant $m$ changes nothing about which factorisations exist over $\mathbb{Q}$ (constants are units there), but it drags the whole problem into $\mathbb{Z}[x]$ where integer-flavoured tools like divisibility and reduction mod $p$ become available. So the working method for any $\mathbb{Q}[x]$ question is always:

• multiply through by the LCM $m$ of the denominators;
• divide out the GCD of the resulting integer coefficients, so that the polynomial is primitive;
• test the resulting integer polynomial with the tests below;
• report the answer back in $\mathbb{Q}[x]$, unchanged.

Example. Show that $f(x)=\frac{1}{2}{x}^3+\frac{2}{5}{x}^2-x+\frac{3}{4}$ is irreducible in $\mathbb{Q}[x]$.
The denominators are $2,5,1$ and $4$, whose lowest common multiple is $m=20$. By Corollary 7.22 it suffices to test

$$\begin{array}{rl}20f(x)& =20\cdot \frac{1}{2}{x}^3+20\cdot \frac{2}{5}{x}^2-20x+20\cdot \frac{3}{4}\\ & =10x^3+8x^2-20x+15,\end{array}$$

and since $\gcd (10,8,20,15)=1$ this is primitive, so by Theorem 7.21 irreducibility in $\mathbb{Z}[x]$ and in $\mathbb{Q}[x]$ are the same question. The degree is $3$, so any nontrivial factorisation must contain a linear factor $ax+b$, which contributes the rational root $-b/a$; so it is enough to show there are no rational roots.

By the rational root theorem (Theorem 7.25 below), every rational root is $\frac{p}{q}$ in simplest form with $p\mid 15$ and $q\mid 10$; that is

$$p\in \{\pm 1,\pm 3,\pm 5,\pm 15\},q\in \{1,2,5,10\},$$

which after discarding pairs with $\gcd (p,q)\ne 1$ leaves $24$ candidates. Grinding through all $24$ is possible but miserable, so we filter them first. Multiplying $f(p/q)=0$ through by $q^3$ turns it into a Diophantine equation:

$$10p^3+8p^{2}q-20p{q}^2+15q^3=0.$$

Reducing that equation mod $2$ kills the first three terms and leaves

$$\begin{array}{rl}15q^3& \equiv 0(\mathrm{mod}2),\\ q^3& \equiv 0(\mathrm{mod}2),\end{array}$$

so $q$ must be even, i.e. $q\in \{2,10\}$. Reducing the same equation mod $5$ kills the first, third and fourth terms and leaves

$$\begin{array}{rl}8p^{2}q& \equiv 0(\mathrm{mod}5),\\ 3p^{2}q& \equiv 0(\mathrm{mod}5),\end{array}$$

so $5\mid p^{2}q$, and since $5$ is prime this means $5\mid p$ or $5\mid q$. Combining: if $q=2$ then $5\nmid q$, so we need $5\mid p$, giving $p\in \{\pm 5,\pm 15\}$; if $q=10$ then $5\mid q$ already, but $\gcd (p,10)=1$ forces $p\in \{\pm 1,\pm 3\}$. Only eight candidates survive, and we test them in the integer form $N(p,q)=10p^3+8p^{2}q-20p{q}^2+15q^3$:

For instance the $p=-5$, $q=2$ entry unpacks as

$$\begin{array}{rl}N(-5,2)& =10(-125)+8(25)(2)-20(-5)(4)+15(8)\\ & =-1250+400+400+120\\ & =-330\ne 0.\end{array}$$

Not one of the eight gives $0$, so $10x^3+8x^2-20x+15$ has no rational roots, hence no linear factor, hence (being cubic) no nontrivial factorisation at all. Therefore $f(x)$ is irreducible in $\mathbb{Q}[x]$. Notice how two one-line congruences threw away two thirds of the candidate list before we did any real arithmetic; when the rational root theorem hands you a long candidate list, reduce the Diophantine relation modulo the small primes dividing $a_0$ and $a_n$ first.

Testing by the Degrees of the Factors

When we test an integer $n$ for primality we only trial-divide up to $\sqrt{n}$, because in any factorisation $n=ab$ the smaller factor is at most $\sqrt{n}$. Degrees add where integer sizes multiply, so the polynomial version replaces n​ with "half".

Proof. Let $\mathrm{deg}(f(x))=n>0$ and suppose $f(x)$ is not irreducible, so we can write $f(x)=g(x)h(x)$ where neither $g(x)$ nor $h(x)$ is a unit. Over a field the units are exactly the nonzero constants, so $\mathrm{deg}(g(x))\ge 1$ and $\mathrm{deg}(h(x))\ge 1$; and since degrees add,

$$\mathrm{deg}(g(x))+\mathrm{deg}(h(x))=n.$$

Relabel if necessary so that $\mathrm{deg}(g(x))\le \mathrm{deg}(h(x))$. Then

$$\begin{array}{rl}2\mathrm{deg}(g(x))& \le \mathrm{deg}(g(x))+\mathrm{deg}(h(x))\\ & =n,\\ \mathrm{deg}(g(x))& \le \frac{1}{2}n,\end{array}$$

and $\mathrm{deg}(g(x))\ge 1$ as noted. $■$

We can restrict to irreducible $g(x)$ because any factor in that degree range itself has an irreducible factor of no larger degree (by unique factorisation, Theorem 7.6), and that irreducible one divides $f(x)$ too; and we can restrict to monic $g(x)$ because multiplying a factor by a unit does not change what it divides. When $R$ is finite — for example $R={\mathbb{Z}}_n$ — there are only finitely many monic polynomials of each degree, so this is a genuinely finite test that a computer (or a patient student) can just run.

This corollary is also where the degree $2$ and $3$ rule finally gets its proper justification: if $n\in \{2,3\}$ then $\frac{n}{2}<2$, so the only candidate divisors are the monic linear ones $x-a$, and $(x-a)\mid f(x)$ exactly when $a$ is a root. Hence

$$\boxed{\text{for }\mathrm{deg}(f(x))\in \{2,3\}\text{ over a field: }f(x)\text{ is irreducible}⟺f(x)\text{ has no roots.}}$$

For $n=4$ or $5$ you additionally have to try every monic irreducible quadratic, for $n=6$ or $7$ every monic irreducible cubic as well, and so on.

Example. Show that $f(x)=x^3+x^2+x+2$ is irreducible in ${\mathbb{Z}}_3[x]$.
Here $n=3$, so $\frac{n}{2}=1.5$ and the finite test only asks about monic linear divisors $x-a$ with $a\in {\mathbb{Z}}_3$; equivalently, about roots. Substituting each of the three elements of ${\mathbb{Z}}_3$:

$$\begin{array}{rl}f(0)& =0+0+0+2=2,\\ f(1)& =1+1+1+2=5=2,\\ f(2)& =8+4+2+2=16=1\text{ in }{\mathbb{Z}}_3.\end{array}$$

None of the values is $0$, so $f(x)$ has no roots in ${\mathbb{Z}}_3$ and therefore no linear factor. Therefore $x^3+x^2+x+2$ is irreducible in ${\mathbb{Z}}_3[x]$. Note that we were entitled to stop after checking roots only because the degree is $3$; had the degree been $4$ we would also have had to divide by each of the monic irreducible quadratics $x^2+1$, $x^2+x+2$ and $x^2+2x+2$.

The Rational Root Theorem

Over ${\mathbb{Z}}_p$ we can hunt for roots by brute force. Over $\mathbb{Q}$ there are infinitely many candidates, so we need a theorem that cuts the search down to a finite list — and it is the same divisibility argument you would use on any Diophantine equation.

Proof. Let $\frac{p}{q}$ be a rational root in simplest form, so $f\left(\frac{p}{q}\right)=0$ and $\gcd (p,q)=1$. Multiplying through by $q^n$ clears every denominator:

$$\begin{array}{rl}\sum _{i=0}^n{a}_i\frac{p^i}{q^i}& =0,\\ \sum _{i=0}^n{a}_i{p}^i{q}^{n-i}& =0,\\ a_n{p}^n+a_{n-1}{p}^{n-1}q+\cdots +a_{1}p{q}^{n-1}+a_0{q}^n& =0,\end{array}$$

which is now an equation between integers. Isolating the last term,

$$\begin{array}{rl}{a}_0{q}^n& =-p\left(a_n{p}^{n-1}+a_{n-1}{p}^{n-2}q+\cdots +a_1{q}^{n-1}\right),\end{array}$$

so $p\mid a_0{q}^n$. Since $\gcd (p,q)=1$ we also have $\gcd (p,q^n)=1$, so $p$ shares no factor with $q^n$ and therefore $p\mid a_0$. Symmetrically, isolating the first term,

$$\begin{array}{rl}{a}_n{p}^n& =-q\left(a_{n-1}{p}^{n-1}+a_{n-2}{p}^{n-2}q+\cdots +a_0{q}^{n-1}\right),\end{array}$$

so $q\mid a_n{p}^n$, and $\gcd (q,p^n)=1$ forces $q\mid a_n$. $■$

Basically, the denominator of a rational root can only be built out of the leading coefficient and the numerator only out of the constant term; everything in the middle is irrelevant. The hypothesis $a_0\ne 0$ matters — if the constant term is $0$ then $x$ is a factor and $x=0$ is a root, which the theorem would otherwise miss (every integer divides $0$, so the candidate list would be infinite). Factor out the largest power of $x$ first. A very common special case worth remembering separately:

$$\boxed{\text{if }f(x)\text{ is monic, then }q\mid 1,\text{ so every rational root is an integer dividing }{a}_0.}$$

Example. Show that $f(x)=x^3+x^2+x+2$ is irreducible in $\mathbb{Q}[x]$.
The coefficients are integers with $\gcd (1,1,1,2)=1$, so $f(x)$ is primitive and by Theorem 7.21 we may work in $\mathbb{Z}[x]$. The degree is $3$, so $f(x)$ is reducible if and only if it has a rational root. By the rational root theorem with $a_0=2$ and $a_n=1$ we need $p\mid 2$ and $q\mid 1$, so $q=1$ and the only candidates are the integers $\pm 1,\pm 2$:

$$\begin{array}{rl}f(1)& =1+1+1+2=5,\\ f(-1)& =-1+1-1+2=1,\\ f(2)& =8+4+2+2=16,\\ f(-2)& =-8+4-2+2=-4.\end{array}$$

None of these is $0$, so $f(x)$ has no rational roots and hence no linear factor. Therefore $x^3+x^2+x+2$ is irreducible in $\mathbb{Q}[x]$ (and, being primitive, in $\mathbb{Z}[x]$). Notice that we have now proved this same polynomial irreducible over both ${\mathbb{Z}}_3$ and $\mathbb{Q}$; the next section explains why the first of those facts was already enough on its own.

Reducing Modulo a Prime

Checking four candidate roots was fine, but for larger coefficients the candidate list explodes. The fix is the same one we used all through Polynomial Congruences: push the problem into ${\mathbb{Z}}_n$, where there are only finitely many things to try.

Proof. We prove the contrapositive. Suppose $f(x)={\sum }_{i=0}^n{a}_i{x}^i$ has an integer root $b$, so $f(b)=0$. Reduction mod $n$ respects both addition and multiplication (this is exactly the point of Modular Arithmetic), so writing $\bar{c}$ for the class of $c$ in ${\mathbb{Z}}_n$,

$$\begin{array}{rl}\bar{f}(\bar{b})& =\sum _{i=0}^n\overline{a_i}{\bar{b}}^i\\ & =\overline{\sum _{i=0}^n{a}_i{b}^i}\\ & =\overline{f(b)}\\ & =\bar{0}.\end{array}$$

So $\bar{b}$ is a root of the reduced polynomial in ${\mathbb{Z}}_n$. Hence if there is no root in ${\mathbb{Z}}_n$, there can be no root in $\mathbb{Z}$. $■$

Basically, a root survives reduction; so if the shadow has no roots, neither does the original. The same idea upgrades from roots to whole factorisations, provided the leading coefficient survives.

Proof. Again we prove the contrapositive: if $f(x)$ is reducible in $\mathbb{Z}[x]$ then it is reducible in ${\mathbb{Z}}_p[x]$. Suppose $f(x)=g(x)h(x)$ with $g(x),h(x)\in \mathbb{Z}[x]$, neither a unit of $\mathbb{Z}[x]$. Since $f(x)$ is primitive, neither factor can be a constant (a constant factor $c$ would divide every coefficient of $f(x)$, forcing $c=\pm 1$), so $\mathrm{deg}(g(x))\ge 1$ and $\mathrm{deg}(h(x))\ge 1$.

Let $a_n$ be the leading coefficient of $f(x)$, and $b,c$ the leading coefficients of $g(x),h(x)$; then $a_n=bc$. Since $p\nmid a_n$ and $p$ is prime, $p\nmid b$ and $p\nmid c$, so neither leading coefficient dies when we reduce mod $p$:

$$\mathrm{deg}(\bar{g}(x))=\mathrm{deg}(g(x))\ge 1,\mathrm{deg}(\bar{h}(x))=\mathrm{deg}(h(x))\ge 1.$$

Reduction respects multiplication, so $\bar{f}(x)=\bar{g}(x)\bar{h}(x)$; and since the units of ${\mathbb{Z}}_p[x]$ are just the nonzero constants, neither $\bar{g}(x)$ nor $\bar{h}(x)$ is a unit. Hence $\bar{f}(x)$ is reducible in ${\mathbb{Z}}_p[x]$. $■$

The condition $p\nmid a_n$ is not decoration. If $p$ kills the leading coefficient then the degree collapses on reduction and the argument breaks: for example $3x^2+x$ reduces mod $3$ to the linear polynomial $x$, which is irreducible in ${\mathbb{Z}}_3[x]$, yet $3x^2+x=x(3x+1)$ is obviously reducible in $\mathbb{Z}[x]$.

The converse of Theorem 7.27 is false, and this is the trap. A polynomial can be perfectly irreducible over $\mathbb{Z}$ and still factor modulo some prime; we saw exactly this above, where $x^2+1$ is irreducible in $\mathbb{Z}[x]$ but $x^2+1=(x+2)(x+3)$ in ${\mathbb{Z}}_5[x]$. So a reduction that factors proves absolutely nothing — you have learned only that this particular prime was a bad choice, and you must go and try another one. A reduction that is irreducible is the only outcome that settles the question.

Example. Show that $f(x)=3x^3+4x^2+6x-5$ is irreducible in $\mathbb{Z}[x]$.
The coefficients have GCD $1$, so $f(x)$ is primitive, and the leading coefficient is $a_3=3$. Straight away $p=3$ is off the table, since $3\mid a_3$. We work through the remaining small primes.

Try $p=2$. Reducing coefficients mod $2$ gives $3\equiv 1$, $4\equiv 0$, $6\equiv 0$, $-5\equiv 1$, so

$$\bar{f}(x)=x^3+1\text{ in }{\mathbb{Z}}_2[x].$$

But $\bar{f}(1)=1+1=0$, so $x+1$ is a factor; in fact $x^3+1=(x+1)(x^2+x+1)$ in ${\mathbb{Z}}_2[x]$. The reduction is reducible, so this prime tells us nothing.

Try $p=5$. Here $3\equiv 3$, $4\equiv 4$, $6\equiv 1$, $-5\equiv 0$, so

$$\bar{f}(x)=3x^3+4x^2+x=x(3x^2+4x+1)\text{ in }{\mathbb{Z}}_5[x].$$

The leading coefficient did survive ($5\nmid 3$), but the constant term vanished and handed us the root $x=0$. Reducible again; still nothing learned.

Try $p=7$. Now $3\equiv 3$, $4\equiv 4$, $6\equiv 6$ and $-5\equiv 2$, so

$$\bar{f}(x)=3x^3+4x^2+6x+2\text{ in }{\mathbb{Z}}_7[x],$$

and $7\nmid 3$ so the degree is still $3$. Being cubic, it is irreducible exactly when it has no roots, and ${\mathbb{Z}}_7$ is small enough to check exhaustively. Building the table from the powers of $x$ first keeps the numbers tiny:

For instance the $a=3$ column is $3(6)+4(2)+6(3)+2=18+8+18+2=46=4$ in ${\mathbb{Z}}_7$. No entry in the bottom row is $0$, so $\bar{f}(x)$ has no roots in ${\mathbb{Z}}_7$ and is therefore irreducible in ${\mathbb{Z}}_7[x]$. Since $7\nmid 3$, Theorem 7.27 applies. Therefore $3x^3+4x^2+6x-5$ is irreducible in $\mathbb{Z}[x]$, and by Theorem 7.21 also in $\mathbb{Q}[x]$.

It is worth dwelling on the fact that we needed three attempts. There is no way to know in advance which prime will work, so treat "reducible mod $p$" as no information at all and just move on to the next prime; only "irreducible mod $p$" ever concludes the argument. As a rule of thumb, take the primes in increasing order, skipping any that divide the leading coefficient, and stop the moment one of them gives an irreducible reduction. (For this particular $f(x)$ the rational root theorem would also have worked — the candidates are $\pm 1,\pm 5,\pm \frac{1}{3},\pm \frac{5}{3}$ and none is a root — but that is eight evaluations with awkward fractions against seven tiny ones mod $7$.)

Eisenstein's Criterion

Sometimes you can read irreducibility straight off the coefficients without testing anything. The pattern to look for is "one prime divides everything except the leading coefficient, and only just divides the constant term".

Proof. Suppose for contradiction that $f(x)$ is reducible. As $f(x)$ is primitive, no constant factor is possible, so we can write

$$f(x)=g(x)h(x),g(x)=\sum _{i=0}^r{b}_i{x}^i,h(x)=\sum _{j=0}^s{c}_j{x}^j,$$

with $r,s\ge 1$ and $r+s=n$. Comparing constant terms gives $a_0=b_0{c}_0$. Now $p\mid a_0$ but $p^2\nmid a_0$, so $p$ divides exactly one of $b_0,c_0$; relabelling if necessary, say

$$p\mid b_0\text{and}p\nmid c_0.$$

Comparing leading coefficients gives $a_n=b_r{c}_s$, and $p\nmid a_n$, so in particular $p\nmid b_r$. Therefore the list $b_0,b_1,\dots ,b_r$ starts with a multiple of $p$ and ends with a non-multiple; let $k$ be the smallest index with $p\nmid b_k$. Then $1\le k\le r$, and since $s\ge 1$ we get $k\le r=n-s\le n-1$.

Now compare the coefficients of $x^k$ on both sides (using the convention $b_i=0$ for $i>r$ and $c_j=0$ for $j>s$):

$$\begin{array}{rl}{a}_k& =b_k{c}_0+b_{k-1}{c}_1+b_{k-2}{c}_2+\cdots +b_0{c}_k.\end{array}$$

Since $k\le n-1$, the hypothesis gives $p\mid a_k$. Every term after the first involves some $b_i$ with $i<k$, and by minimality of $k$ every such $b_i$ is divisible by $p$; so $p$ divides the entire tail. Subtracting, $p\mid b_k{c}_0$. But $p$ is prime and $p\nmid b_k$ and $p\nmid c_0$, so $p\nmid b_k{c}_0$ — a contradiction. Therefore no such factorisation exists and $f(x)$ is irreducible. $■$

Basically, Eisenstein works by watching where the single prime $p$ can go. It has to divide the constant term of one factor but not the other, and then it runs out of room as you climb the coefficients. All three conditions are needed: drop $p^2\nmid a_0$ and the criterion collapses, since $x^2+4x+4=(x+2{)}^2$ passes the first two conditions with $p=2$.

Example. Show that $f(x)=x^3+2x^2+6x+10$ is irreducible in $\mathbb{Z}[x]$.
Try $p=2$ and check the three conditions against $a_0=10$, $a_1=6$, $a_2=2$, $a_3=1$:

$$\begin{array}{rl}2\mid 10,2\mid 6,2\mid 2& (\text{so }p\mid a_i\text{ for }0\le i\le 2),\\ 2\nmid 1& (\text{so }p\nmid a_3),\\ 4\nmid 10& (\text{since }10=4(2)+2).\end{array}$$

All three hold, so by Eisenstein's criterion $f(x)$ is irreducible in $\mathbb{Z}[x]$, and hence also in $\mathbb{Q}[x]$. Notice how little work that was compared with the mod $p$ hunt of the last section; whenever you meet a polynomial whose non-leading coefficients share a prime factor, try Eisenstein before anything else.

Shifting the Variable

Eisenstein is fast but fragile; a polynomial can fail it outright and still be irreducible. The rescue is that irreducibility does not notice a horizontal shift, so if $f(x)$ is not in Eisenstein shape you may be able to move it into shape.

Proof. Substituting $x\mapsto x+a$ is a map $\mathbb{Z}[x]\to \mathbb{Z}[x]$ that respects sums and products, since evaluating a sum or product at $x+a$ is the same as summing or multiplying the evaluations:

$$(gh)(x+a)=g(x+a)h(x+a).$$

It also preserves degree (the leading term $a_n{x}^n$ becomes $a_n(x+a{)}^n$, whose only $x^n$ term is $a_n{x}^n$), and it is undone by the substitution $x\mapsto x-a$.

($\Rightarrow$, contrapositive) Suppose $f(x+a)$ is reducible, say $f(x+a)=g(x)h(x)$ with $\mathrm{deg}(g(x)),\mathrm{deg}(h(x))\ge 1$. Substituting $x\mapsto x-a$ into both sides gives

$$f(x)=g(x-a)h(x-a),$$

and both factors still have degree at least $1$, so $f(x)$ is reducible.
($\Leftarrow$) Identical, running the substitution the other way: if $f(x)=g(x)h(x)$ nontrivially then $f(x+a)=g(x+a)h(x+a)$ nontrivially. $■$

Basically, sliding the graph left or right cannot create or destroy a factorisation; it just relabels one. But the shift does change the coefficients completely, and that is the whole point — Eisenstein looks at coefficients, so a shift can turn an untestable polynomial into a testable one. The usual trick is to try $a=\pm 1$ first, then $a=\pm 2$.

Example. Show that $f(x)=x^3-x^2+5x+5$ is irreducible in $\mathbb{Z}[x]$.
Eisenstein fails as written: the only prime dividing $a_0=5$ is $p=5$, but $5\nmid a_1=5$ is false — no wait, $5\mid 5$ is fine — the failure is at $a_2=-1$, since $5\nmid -1$. So no prime works directly. Instead substitute $x\mapsto x+1$ and expand:

$$\begin{array}{rl}f(x+1)& =(x+1{)}^3-(x+1{)}^2+5(x+1)+5\\ & =(x^3+3x^2+3x+1)-(x^2+2x+1)+5x+5+5\\ & =x^3+(3-1)x^2+(3-2+5)x+(1-1+10)\\ & =x^3+2x^2+6x+10.\end{array}$$