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]^*$ or $g(x) \in R[x]^*$. 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), \qquad \deg(r(x)) < \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{align*} f(a) &= q(a)(a-a) + r \\ &= q(a) \cdot 0 + r \\ &= r. \end{align*}$$

So the remainder is the constant $f(a)$. $\blacksquare$

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{align*} f(2) &= 2^4 + 3(2^2) - 2(2) + 5 \\ &= 16 + 12 - 4 + 5 \\ &= 29. \end{align*}$$

Therefore the remainder is $29$, and since $29 \neq 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{align*} 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{align*}$$

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_1x + a_0$ with $a_1 \neq 0$, and suppose $b$ and $c$ are both roots. Then

$$\begin{align*} a_1b + a_0 &= 0 = a_1c + a_0, \\ a_1b &= a_1c, \\ a_1(b - c) &= 0, \end{align*}$$

and since $a_1 \neq 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 $\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) \quad \text{for some } g(x) \in R[x],$$

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

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

and $b - a \neq 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. $\blacksquare$

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{align*} 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{align*}$$

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_1x + 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 $\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. $\blacksquare$

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 $\deg(f(x)) = 1$ and $f(x) = g(x)h(x)$. Degrees add over a field, so $\deg(g(x)) + \deg(h(x)) = 1$ and one of the two factors has degree $0$, i.e. is a nonzero constant. Since $\mathbb{C}[x]^* = \mathbb{C}^*$, 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 $\deg(f(x)) \geq 1$. If $\deg(f(x)) = n \geq 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), \qquad \deg(g(x)) = n - 1 \geq 1.$$

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

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 $\deg(f(x)) = n \geq 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 $\deg(g(x)) = n - 1 \geq 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 \neq 0$. Writing $f(x) = \sum_{k=0}^n a_kx^k$ with every $a_k \in \mathbb{R}$, and using the fact that conjugation respects sums and products while fixing every real number,

$$\begin{align*} f(\bar{z}) &= \sum_{k=0}^n a_k \bar{z}^{\,k} \\ &= \sum_{k=0}^n \overline{a_k} \, \overline{z^k} \quad (\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{align*}$$

so $\bar{z} = \alpha - \beta i$ is also a root, and $\bar{z} \neq z$ because $\beta \neq 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{align*} (x - z)(x - \bar{z}) &= x^2 - (z + \bar{z})x + z\bar{z} \\ &= x^2 - 2\alpha x + (\alpha^2 + \beta^2), \end{align*}$$

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 $\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), \qquad q(x) \in \mathbb{R}[x], \quad \deg(q(x)) = n - 2 \geq 1,$$

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

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{align*} x^4 - 4 &= (x^2 - 2)(x^2 + 2). \end{align*}$$

(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{align*} (\pm1)^2 - 2 &= -1, & (\pm 2)^2 - 2 &= 2, \\ (\pm1)^2 + 2 &= 3, & (\pm 2)^2 + 2 &= 6, \end{align*}$$

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 \geq 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{align*} f(0) &= 0 + 1 = 1, \\ f(1) &= 1 + 1 = 2, \\ f(2) &= 4 + 1 = 5 = 2 \text{ in } \mathbb{Z}_3. \end{align*}$$

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{align*} (x^2+1)^2 &= x^4 + 2x^2 + 1, \end{align*}$$

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

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

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{align*} x^4 - 4 &= (x^2-2)(x^2+2) \\ &= (x^2+1)(x^2-1) \quad (\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) \quad (\text{since } -1 = 2 \text{ in } \mathbb{Z}_3). \end{align*}$$

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. $\blacksquare$

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) = \dfrac{1}{2}x^3 + \dfrac{2}{5}x^2 - x + \dfrac{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{align*} 20f(x) &= 20 \cdot \tfrac{1}{2}x^3 + 20\cdot\tfrac{2}{5}x^2 - 20x + 20\cdot\tfrac{3}{4} \\ &= 10x^3 + 8x^2 - 20x + 15, \end{align*}$$

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 \{\pm1, \pm3, \pm5, \pm15\}, \qquad q \in \{1, 2, 5, 10\},$$

which after discarding pairs with $\gcd(p,q) \neq 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^2q - 20pq^2 + 15q^3 = 0.$$

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

$$\begin{align*} 15q^3 &\equiv 0 \pmod 2, \\ q^3 &\equiv 0 \pmod 2, \end{align*}$$

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{align*} 8p^2q &\equiv 0 \pmod 5, \\ 3p^2q &\equiv 0 \pmod 5, \end{align*}$$

so $5 \mid p^2q$, 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 \{\pm5, \pm15\}$; if $q = 10$ then $5 \mid q$ already, but $\gcd(p, 10) = 1$ forces $p \in \{\pm1, \pm3\}$. Only eight candidates survive, and we test them in the integer form $N(p,q) = 10p^3 + 8p^2q - 20pq^2 + 15q^3$:

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

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

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 $\sqrt{\phantom{n}}$ with "half".

Proof. Let $\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 $\deg(g(x)) \geq 1$ and $\deg(h(x)) \geq 1$; and since degrees add,

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

Relabel if necessary so that $\deg(g(x)) \leq \deg(h(x))$. Then

$$\begin{align*} 2\deg(g(x)) &\leq \deg(g(x)) + \deg(h(x)) \\ &= n, \\ \deg(g(x)) &\leq \tfrac{1}{2}n, \end{align*}$$

and $\deg(g(x)) \geq 1$ as noted. $\blacksquare$

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 $\tfrac{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 } \deg(f(x)) \in \{2,3\} \text{ over a field: } f(x) \text{ is irreducible} \iff 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 $\tfrac{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{align*} 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{align*}$$

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{align*} \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_np^n + a_{n-1}p^{n-1}q + \cdots + a_1pq^{\,n-1} + a_0q^n &= 0, \end{align*}$$

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

$$\begin{align*} a_0q^n &= -p\left(a_np^{n-1} + a_{n-1}p^{n-2}q + \cdots + a_1q^{\,n-1}\right), \end{align*}$$

so $p \mid a_0q^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{align*} a_np^n &= -q\left(a_{n-1}p^{n-1} + a_{n-2}p^{n-2}q + \cdots + a_0q^{\,n-1}\right), \end{align*}$$

so $q \mid a_np^n$, and $\gcd(q, p^n) = 1$ forces $q \mid a_n$. $\blacksquare$

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 \neq 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 $\pm1, \pm2$: