Irreducible Polynomials and Roots

The primes of a polynomial ring. Irreducible polynomials over a field, Euclid's lemma and unique factorization for polynomials, the remainder and factor theorems, why a polynomial of degree n has at most n roots and how that fails modulo 15, x^p - x as the product of all linear factors over Z_p with Wilson's theorem as a corollary, the root test for degrees 2 and 3, and over the rationals the rational root test, Gauss's lemma, Eisenstein's criterion and reduction modulo a prime, ending with the irreducible polynomials over the reals and the complex numbers.

The running example of this unit,

$$f(x) = x^4 + x^3 - x^2 - 2x - 2,$$

has no rational roots. If $f(r/s) = 0$ for a fraction in lowest terms, the rational root test proved below forces $r$ to divide $-2$ and $s$ to divide 1, so the only candidates are $\pm 1$ and $\pm 2$, and the values there are $f(1) = -3$, $f(-1) = -1$, $f(2) = 14$ and $f(-2) = 6$. Yet $f(x)$ is not "prime" among polynomials with rational coefficients, because

$$f(x) = (x^2 - 2)(x^2 + x + 1).$$

Neither factor can be split further using rational coefficients. With real coefficients the first one can, as $(x - \sqrt{2})(x + \sqrt{2})$, and with complex coefficients both can, so that $f(x)$ becomes a product of four linear factors. With coefficients in $\mathbb{Z}_7$ it also splits completely, with a repeated factor, while in $\mathbb{Z}_{11}$ it splits into two quadratics that go no further. So which polynomials are the "primes", and how can we recognize them over a given field?

The running example f(x) = (x^2 - 2)(x^2 + x + 1). Left: notice that its graph over the reals crosses the axis only at \pm\sqrt{2} (circles), and that all four candidates for a rational root (squares, x = 2 off the plot at f(2) = 14) miss. Right: its four roots in the complex plane, the real pair from x^2 - 2 and the conjugate pair \omega, \bar\omega on the unit circle from x^2 + x + 1. Over \mathbb{Q} the two quadratics cannot be split, over \mathbb{R} only the first can, and over \mathbb{C} both can.
The running example $f(x) = (x^2 - 2)(x^2 + x + 1)$. Left: notice that its graph over the reals crosses the axis only at $\pm\sqrt{2}$ (circles), and that all four candidates for a rational root (squares, $x = 2$ off the plot at $f(2) = 14$) miss. Right: its four roots in the complex plane, the real pair from $x^2 - 2$ and the conjugate pair $\omega$, $\bar\omega$ on the unit circle from $x^2 + x + 1$. Over $\mathbb{Q}$ the two quadratics cannot be split, over $\mathbb{R}$ only the first can, and over $\mathbb{C}$ both can.

The polynomials that cannot be split are the irreducible polynomials, and they play the part of the prime numbers.

First we prove the polynomial version of the fundamental theorem of arithmetic: over a field, every nonconstant polynomial is a product of irreducibles in essentially one way. Then we connect roots to linear factors. Next come the tests for irreducibility: roots in degrees 2 and 3, then four tests over the rationals. Finally the fundamental theorem of algebra settles the real and complex numbers.

This is the last article of Polynomial Arithmetic. It assumes polynomial division over a field, especially cancellation, and covers §§4.3 to 4.6 of the course text (Hungerford, 2014). Throughout, $F$ is a field.

Irreducible polynomials

In the integers, the units $\pm 1$ divide everything, and every integer $n$ is divisible by $\pm 1$ and $\pm n$. A prime is an integer with no other divisors. In $F[x]$ the units are the nonzero constants, every nonzero constant divides every polynomial, and every polynomial is divisible by its associates, its nonzero constant multiples.

Definition. A nonconstant polynomial $p(x) \in F[x]$ is irreducible if its only divisors are the nonzero constants and the associates of $p(x)$. A nonconstant polynomial that is not irreducible is reducible.

Constant polynomials are neither, just as $0$, $1$ and $-1$ are neither prime nor composite. The definition describes an irreducible by its divisors. An equivalent description by degrees is easier to use, and the idea behind it is simple: a divisor that is neither a constant nor an associate is exactly a factor of strictly intermediate degree.

Theorem. A nonconstant polynomial $f(x) \in F[x]$ is irreducible if and only if it cannot be written as a product $g(x)h(x)$ of two polynomials of lower degree.

Proof. Suppose $f = gh$ with $\deg g < \deg f$ and $\deg h < \deg f$. Since $\deg g + \deg h = \deg f$, both $g$ and $h$ have positive degree. Then $g$ is a divisor of $f$ that is not a nonzero constant (its degree is positive) and not an associate of $f$ (associates have equal degree). So $f$ is reducible.

Conversely, suppose $f$ is reducible, so it has a divisor $g$ that is neither a nonzero constant nor an associate of $f$; write $f = gh$. Then $\deg g \ge 1$. If $\deg g = \deg f$, then $\deg h = 0$, so $h$ is a nonzero constant $c$ and $g = c^{-1}f$ is an associate of $f$, which was excluded. So $1 \le \deg g < \deg f$, and therefore $\deg h = \deg f - \deg g$ satisfies $1 \le \deg h < \deg f$ as well. $\blacksquare$

This is Hungerford's Theorem 4.11. Two consequences are immediate. Every polynomial of degree 1 is irreducible, since it cannot be a product of two polynomials of degree 0 or less. And whether a polynomial is irreducible depends on the field: $x^2 - 2$ is irreducible in $\mathbb{Q}[x]$, as the root test below shows, but reducible in $\mathbb{R}[x]$.

Euclid's lemma for polynomials

For integers, a prime was defined by its divisors, and Euclid's lemma showed that it is also characterized by a property of its multiples: if it divides a product, it divides a factor. The same holds in $F[x]$. The idea is that an irreducible either divides a polynomial or shares nothing with it, and in the second case cancellation applies.

Theorem. Let $p(x) \in F[x]$ be nonconstant. Then $p(x)$ is irreducible if and only if, whenever $p(x) \mid b(x)c(x)$ for polynomials $b(x)$ and $c(x)$, then $p(x) \mid b(x)$ or $p(x) \mid c(x)$.

Proof. Suppose $p$ is irreducible, $p \mid bc$ and $p \nmid b$. The greatest common divisor $d = \gcd(p, b)$ divides $p$, so it is a nonzero constant or an associate of $p$. It cannot be an associate of $p$: then $p$ would divide $d$, and $d$ divides $b$, so $p \mid b$. So $d$ is a monic constant, $d = 1$, and the cancellation theorem (if $a \mid bc$ and $\gcd(a, b) = 1$ then $a \mid c$) gives $p \mid c$.

Conversely, suppose $p$ has the product property, and suppose $p = rs$ for some polynomials $r$ and $s$. Then $p \mid rs$, so $p \mid r$ or $p \mid s$; say $p \mid r$. Since also $r \mid p$, the degrees satisfy $\deg p \le \deg r \le \deg p$, so $\deg r = \deg p$ and $\deg s = 0$. Hence $p$ is not a product of two polynomials of lower degree, and it is irreducible by the previous theorem. $\blacksquare$

Corollary. If $p(x)$ is irreducible and $p(x) \mid a_1(x) a_2(x) \cdots a_n(x)$, then $p(x) \mid a_i(x)$ for some $i$.

Proof. By induction on $n$, exactly as for integers: write the product as $(a_1 \cdots a_{n-1}) \cdot a_n$ and apply the theorem. $\blacksquare$

These are Hungerford's Theorem 4.12 and Corollary 4.13. The proofs are the integer proofs, with "a positive divisor of $p$ is 1 or $\lvert p \rvert$" replaced by "a monic divisor of $p$ is 1 or the monic associate of $p$".

Unique factorization

The proof follows the integer proof. Existence takes a counterexample of least degree and splits it. Uniqueness uses Euclid's lemma to match one irreducible on each side, cancels it, and repeats.

Theorem (unique factorization in $F[x]$). Every nonconstant polynomial $f(x) \in F[x]$ is a product of irreducible polynomials. The factorization is unique in this sense: if

$$f(x) = p_1(x) p_2(x) \cdots p_r(x) = q_1(x) q_2(x) \cdots q_s(x)$$

with every $p_i$ and $q_j$ irreducible, then $r = s$, and after the $q_j$ are renumbered, each $q_i$ is an associate of $p_i$.

Proof of existence. Suppose some nonconstant polynomials are not products of irreducibles. By the well-ordering principle, among them there is one of least degree, $f$. It is not irreducible (an irreducible is a product of one irreducible), so $f = gh$ with $g$ and $h$ of lower, positive degree. By the choice of $f$, both $g$ and $h$ are products of irreducibles, and so is $f = gh$, a contradiction.

Proof of uniqueness. By induction on $r$. If $r = 1$, then $p_1 = q_1 \cdots q_s$ is irreducible. If $s \ge 2$, it would be the product of $q_1$ and $q_2 \cdots q_s$, both of positive degree and so of lower degree than $p_1$, contradicting irreducibility; so $s = 1$ and $q_1 = p_1$.

Now let $r \ge 2$ and assume the statement for products of $r - 1$ irreducibles. Since $p_1$ divides $q_1 q_2 \cdots q_s$, the corollary gives $p_1 \mid q_j$ for some $j$; renumber so that $j = 1$. As $q_1$ is irreducible and $p_1$ is not a constant, $p_1$ is an associate of $q_1$: $q_1 = c\, p_1$ for a nonzero constant $c$. Substituting and canceling the nonzero factor $p_1$, which is allowed in the integral domain $F[x]$, gives

$$p_2 p_3 \cdots p_r = (c\, q_2) q_3 \cdots q_s.$$

Here $s \ge 2$, since otherwise the right side would be the constant $c$ while the left side has positive degree. The polynomial $c\,q_2$ is an associate of an irreducible, so it is irreducible. The left side is a product of $r - 1$ irreducibles, so by the induction hypothesis $r - 1 = s - 1$ and, after renumbering, $p_2, \ldots, p_r$ are associates of $c\,q_2, q_3, \ldots, q_s$ in order. An associate of $c\,q_2$ is an associate of $q_2$, which completes the induction. $\blacksquare$

This is Hungerford's Theorem 4.14. As with integers, "unique" can only mean unique up to order and up to associates: $x^2 - 1 = (x - 1)(x + 1) = (3x - 3)(5x + 5)$ in $\mathbb{Z}_7[x]$, because $3 \cdot 5 = 15 = 1$ there. The ambiguity disappears with a normal form. Write each irreducible factor as a constant times its monic associate, and collect the constants. Comparing leading coefficients shows that their product is the leading coefficient of $f$. So

$$f(x) = c\, p_1(x) p_2(x) \cdots p_r(x), \qquad c = \text{leading coefficient of } f, \quad p_i \text{ monic irreducible},$$

and by the theorem the monic irreducibles $p_i$ are determined by $f$ up to order, since two monic associates are equal. This is the counterpart of writing an integer as $\pm 1$ times a product of positive primes.

In $\mathbb{Z}$ In $F[x]$
absolute value $\lvert n \rvert$ degree $\deg f$
units $\pm 1$ nonzero constants
$n$ and $-n$ $f$ and its constant multiples (associates)
positive integers monic polynomials
primes irreducible polynomials
$n = \pm\, p_1 \cdots p_r$ $f = c\, p_1 \cdots p_r$

For example, $g(x) = x^4 - 2x^2 - 3x - 2$ has the factorization $(x - 2)(x + 1)(x^2 + x + 1)$ into monic irreducibles in $\mathbb{Q}[x]$, found in the next section from the roots 2 and $-1$, and the running example is $f(x) = (x^2 - 2)(x^2 + x + 1)$. Comparing the two factorizations recovers the greatest common divisor $x^2 + x + 1$ that the Euclidean algorithm computed for this pair without factoring anything.

Roots and linear factors

The factorization of $g$ above comes from its roots 2 and $-1$. Why does a root give a factor? Let $c \in F$. A root (or zero) of $f(x) \in F[x]$ is an element $c$ with $f(c) = 0$, where $f(c)$ is the value defined in polynomial rings, computed by substituting $c$ for $x$.

The idea is to divide by $x - c$ and then substitute $c$, which kills the quotient term and leaves the remainder.

Theorem (remainder theorem). The remainder when $f(x)$ is divided by $x - c$ is the constant $f(c)$.

Proof. By the division algorithm, $f(x) = (x - c)q(x) + r(x)$ with $r(x)$ either 0 or of degree less than 1, so in either case $r(x)$ is a constant $r$. Evaluation at $c$ respects sums and products, so $f(c) = (c - c)q(c) + r = r$. $\blacksquare$

Theorem (factor theorem). $c$ is a root of $f(x)$ if and only if $x - c$ divides $f(x)$ in $F[x]$.

Proof. By the remainder theorem, $f(x) = (x - c)q(x) + f(c)$. If $f(c) = 0$, then $x - c$ divides $f(x)$. Conversely, if $f(x) = (x - c)k(x)$, then $f(c) = 0 \cdot k(c) = 0$. $\blacksquare$

These are Hungerford's Theorems 4.15 and 4.16 and Judson's Corollary 17.2.3. For $g(x) = x^4 - 2x^2 - 3x - 2$, dividing by $x - 3$ gives quotient $x^3 + 3x^2 + 7x + 18$ and remainder 52, and indeed $g(3) = 81 - 18 - 9 - 2 = 52$. The quotient and remainder can be read off from the running totals of Horner's rule for $g(3)$, which on the coefficients $1, 0, -2, -3, -2$ produces $1, 3, 7, 18, 52$. This bookkeeping is the "synthetic division" of school algebra.

Since $g(2) = 0$ and $g(-1) = 0$, the factor theorem gives the factors $x - 2$ and $x + 1$. Dividing them out leaves $x^2 + x + 1$, which has no rational root (its candidates $\pm 1$ give 3 and 1) and so is irreducible by the test for degree 2 below. That proves $g(x) = (x - 2)(x + 1)(x^2 + x + 1)$ is its factorization into irreducibles.

At most $n$ roots

Each root splits off a linear factor and lowers the degree by one, so the roots cannot outnumber the degree. The one subtle point is that a second root of $f$ must be a root of what remains.

Theorem. A nonzero polynomial of degree $n$ in $F[x]$ has at most $n$ roots in $F$.

Proof. By induction on $n$. A polynomial of degree 0 is a nonzero constant and has no roots. Let $n \ge 1$ and assume the result for degree $n - 1$. If $f$ has no roots there is nothing to prove. Otherwise let $c$ be a root, and write $f(x) = (x - c)q(x)$ by the factor theorem, where $\deg q = n - 1$. If $d \neq c$ is another root, then $0 = f(d) = (d - c)q(d)$ with $d - c \neq 0$, and since a field has no zero divisors, $q(d) = 0$. So every root of $f$ other than $c$ is a root of $q$, of which there are at most $n - 1$, and $f$ has at most $n$ roots. $\blacksquare$

This is Hungerford's Corollary 4.17 and Judson's Corollary 17.2.4. The proof used one property of $F$, the absence of zero divisors, and without it the theorem fails already in degree 1. In $\mathbb{Z}_{15}$ the polynomial $5x$ has degree 1, since $5 \neq 0$, yet it has the five roots 0, 3, 6, 9 and 12, because $5c$ is a multiple of 15 exactly when 3 divides $c$. The step that fails is $(d - c)q(d) = 0 \Rightarrow q(d) = 0$. With the root $c = 0$, the factor theorem's factorization is $5x = (x - 0) \cdot 5$, so $q$ is the constant 5, and the second root $d = 3$ gives $(3 - 0) \cdot 5 = 15 = 0$ although neither factor is 0. Over a field, by contrast, $ax$ with $a \neq 0$ has only the root 0. The integral domains article met the same failure in degree 2, with eight solutions of $x^2 = 1$ in $\mathbb{Z}_{24}$.

Corollary. If $F$ is infinite and $f(x), g(x) \in F[x]$ satisfy $f(c) = g(c)$ for every $c \in F$, then $f(x) = g(x)$.

Proof. Every element of $F$ is a root of $f - g$, so $f - g$ has infinitely many roots. By the theorem it is not a nonzero polynomial, so $f = g$. $\blacksquare$

This is Hungerford's Corollary 4.20, and it settles the question left open in Polynomial Rings: over an infinite field such as $\mathbb{Q}$, $\mathbb{R}$ or $\mathbb{C}$, a polynomial and its polynomial function determine each other, so the distinction between them is harmless. Over a finite field it is not.

Check your understanding. Over $\mathbb{Z}_5$, the polynomials $x^6$ and $x^2$ define the same function. Which step of the corollary's proof breaks down?

The step that needs infinitely many roots. Here $f - g = x^6 - x^2$ has every element of $\mathbb{Z}_5$ as a root, but that is only 5 roots for a polynomial of degree 6, which the theorem allows.

$x^p - x$ over $\mathbb{Z}_p$

Polynomial rings showed that $x^6$ and $x^2$ define the same function on $\mathbb{Z}_5$, by Fermat's little theorem. The same theorem says that $a^p = a$ for every $a$ in $\mathbb{Z}_p$, so the nonzero polynomial $x^p - x$ has every element of $\mathbb{Z}_p$ as a root. Roots explain the whole pattern. The idea is that $x^p - x$ and the product of all $x - a$ are monic of the same degree and share $p$ roots, so their difference has lower degree and too many roots.

Proposition. Let $p$ be a prime. In $\mathbb{Z}_p[x]$,

$$x^p - x = x(x - 1)(x - 2) \cdots (x - (p - 1)) = \prod_{a \in \mathbb{Z}_p} (x - a).$$

Proof. Let $h(x)$ be the product on the right. Both $h(x)$ and $x^p - x$ are monic of degree $p$, so their difference has degree less than $p$, or is 0. Every $a \in \mathbb{Z}_p$ is a root of $h$, visibly, and of $x^p - x$, by Fermat's little theorem $a^p = a$. So the difference has all $p$ elements of $\mathbb{Z}_p$ as roots. A nonzero polynomial of degree less than $p$ has fewer than $p$ roots, so the difference is 0. $\blacksquare$

For $p = 5$ the script expands the product over the integers, $x(x - 1)(x - 2)(x - 3)(x - 4) = x^5 - 10x^4 + 35x^3 - 50x^2 + 24x$, and reduces it modulo 5 to $x^5 + 4x = x^5 - x$; it confirms the identity for every prime up to 13. Comparing coefficients gives more. The coefficient of $x$ in $x \prod_{a=1}^{p-1}(x - a)$ is $\prod_{a=1}^{p-1}(-a) = (-1)^{p-1}(p - 1)!$, and in $x^p - x$ it is $-1$. For odd $p$ the sign $(-1)^{p-1}$ is 1, so

$$(p - 1)! \equiv -1 \pmod p,$$

which is Wilson's theorem, proved there by pairing each unit with its inverse; for $p = 2$ it holds because $1 \equiv -1 \pmod 2$. For $p = 5$ the coefficient is $24 \equiv -1$, visible in the expansion above. The polynomial $x^{p^n} - x$ plays the same part in the finite fields with $p^n$ elements.

Degrees 2 and 3: irreducible means no roots

How do we recognize an irreducible? The first test uses roots: a factorization in degree 2 or 3 must include a factor of degree 1, which gives a root.

Theorem. Let $f(x) \in F[x]$.

  1. If $\deg f \ge 2$ and $f(x)$ has a root in $F$, then $f(x)$ is reducible.
  2. If $\deg f$ is 2 or 3, then $f(x)$ is irreducible if and only if it has no root in $F$.

Proof. (1) A root $c$ gives $f(x) = (x - c)q(x)$ with $\deg q = \deg f - 1 \ge 1$, a product of two polynomials of lower degree. (2) One direction is (1). Conversely, if $f$ is reducible, it is a product of two polynomials of positive degree whose degrees add to 2 or 3, so one of them has degree 1, say $ax + b$ with $a \neq 0$. Its root $-b/a$ is a root of $f$. $\blacksquare$

These are Hungerford's Corollaries 4.18 and 4.19. Over a finite field, part (2) reduces irreducibility in degrees 2 and 3 to a finite check. For $x^3 + 2x^2 + 4$ in $\mathbb{Z}_{11}[x]$, the values at $0, 1, \ldots, 10$ are

$$4, \; 7, \; 9, \; 5, \; 1, \; 3, \; 6, \; 5, \; 6, \; 4, \; 5,$$

none of them 0, so the cubic is irreducible in $\mathbb{Z}_{11}[x]$. Over $\mathbb{Q}$ the check is not finite as it stands, since there are infinitely many rationals to try, and the rational root test below makes it finite.

Check your understanding. The running example $f(x)$ has no root in $\mathbb{Q}$ and none in $\mathbb{Z}_{11}$. Is it irreducible over either field?

Over neither. Part (2) stops at degree 3, and in degree 4 a polynomial can lack roots because all its factors have degree 2. Over $\mathbb{Q}$, $f = (x^2 - 2)(x^2 + x + 1)$, and in $\mathbb{Z}_{11}[x]$ the script finds $f = (x^2 + x + 1)(x^2 + 9)$.

Irreducibility over the rationals

Over $\mathbb{Q}$ the root test is not yet a finite check, and it says nothing above degree 3. What else can decide? Multiplying by a common denominator gives integer coefficients without changing the factorization (up to associates), so it is enough to consider $f(x) \in \mathbb{Z}[x]$. The integers then supply tools that a bare field does not: divisibility, primes and reduction modulo a prime.

The rational root test

Theorem (rational root test). Let $f(x) = a_n x^n + \cdots + a_1 x + a_0$ have integer coefficients. If a nonzero rational number $r/s$, in lowest terms, is a root of $f(x)$, then $r \mid a_0$ and $s \mid a_n$.

The idea: after clearing denominators, every term but one is a multiple of $r$, so $r$ must divide the remaining one, and the same goes for $s$.

Proof. Substitute $r/s$ and multiply by $s^n$:

$$a_n r^n + a_{n-1} r^{n-1} s + \cdots + a_1 r s^{n-1} + a_0 s^n = 0.$$

Every term except the last is a multiple of $r$, so $r$ divides $a_0 s^n$. Since $\gcd(r, s) = 1$, no prime divides both $r$ and $s^n$ (a prime dividing $s^n$ divides $s$, by Euclid's lemma), so $\gcd(r, s^n) = 1$, and the cancellation theorem for integers gives $r \mid a_0$. In the same way, every term except the first is a multiple of $s$, so $s \mid a_n r^n$, and since $\gcd(s, r^n) = 1$, $s \mid a_n$. $\blacksquare$

The test produces a finite list of candidates. For the cubic $c(x) = 2x^3 + 3x^2 - x + 5$, the numerator divides 5 and the denominator divides 2, so the candidates are $\pm 1, \pm 5, \pm \tfrac{1}{2}, \pm \tfrac{5}{2}$, and the values there are

$t$ $-5$ $-\tfrac{5}{2}$ $-1$ $-\tfrac{1}{2}$ $\tfrac{1}{2}$ $1$ $\tfrac{5}{2}$ $5$
$c(t)$ $-165$ $-5$ $7$ $6$ $\tfrac{11}{2}$ $9$ $\tfrac{105}{2}$ $325$

None is 0, so $c(x)$ has no rational root, and being of degree 3, it is irreducible in $\mathbb{Q}[x]$. It does have a real root, between $-\tfrac{5}{2}$ and $-1$ where the values change sign, at about $-2.228028$; the test shows that this root is irrational. The test only lists candidates: $2x^2 - 3x - 2$ has the candidates $\pm 1, \pm 2, \pm \tfrac{1}{2}$, and two of them, $2$ and $-\tfrac{1}{2}$, are roots, because $2x^2 - 3x - 2 = (2x + 1)(x - 2)$. The rational root test is Hungerford's Theorem 4.21.

Gauss's lemma

A factorization over $\mathbb{Q}$ may involve fractions, and the running example has one:

$$f(x) = \Big(\tfrac{2}{3}x^2 - \tfrac{4}{3}\Big)\Big(\tfrac{3}{2}x^2 + \tfrac{3}{2}x + \tfrac{3}{2}\Big).$$

Of course $f(x)$ also factors with integer coefficients, as $(x^2 - 2)(x^2 + x + 1)$. Gauss's lemma says that this always happens: a polynomial with integer coefficients that factors over $\mathbb{Q}$ factors over $\mathbb{Z}$, with factors of the same degrees. The plan is to clear denominators and then remove the extra multiplier one prime at a time. Each prime can be removed because of a lemma about reduction modulo a prime $p$, which replaces each coefficient of a polynomial in $\mathbb{Z}[x]$ by its class in $\mathbb{Z}_p$. Write $\bar{g}(x)$ for the reduction of $g(x)$.

Lemma. Reduction modulo $p$ respects sums and products: $\overline{g + h} = \bar g + \bar h$ and $\overline{gh} = \bar g\, \bar h$. Consequently, if a prime $p$ divides every coefficient of a product $g(x)h(x)$ in $\mathbb{Z}[x]$, then $p$ divides every coefficient of $g(x)$ or every coefficient of $h(x)$.

Proof. The coefficients of $g + h$ and $gh$ are sums of coefficients and sums of products of coefficients, and congruences can be added and multiplied, so reducing before or after the operation gives the same class. For the second statement, the hypothesis says $\overline{gh} = 0$ in $\mathbb{Z}_p[x]$, so $\bar g\, \bar h = 0$. Since $\mathbb{Z}_p$ is a field, $\mathbb{Z}_p[x]$ is an integral domain, so $\bar g = 0$ or $\bar h = 0$, which is the claim. $\blacksquare$

The course text proves the second statement by comparing coefficients directly (Hungerford, 2014, Lemma 4.22); reduction modulo $p$ packages that computation into the single fact that $\mathbb{Z}_p[x]$ has no zero divisors.

Theorem (Gauss's lemma). Let $f(x) \in \mathbb{Z}[x]$. If $f(x)$ is a product of polynomials of degrees $m$ and $n$ in $\mathbb{Q}[x]$, then it is a product of polynomials of degrees $m$ and $n$ in $\mathbb{Z}[x]$.

Proof. Let $f = GH$ with $G, H \in \mathbb{Q}[x]$ of degrees $m$ and $n$. Multiplying $G$ and $H$ by common denominators of their coefficients gives positive integers $c$ and $d$ with $cG$ and $dH$ in $\mathbb{Z}[x]$, so $(cd)f = (cG)(dH)$. Hence there are equations

$$N f(x) = g(x) h(x), \qquad N \text{ a positive integer}, \quad g, h \in \mathbb{Z}[x] \text{ of degrees } m \text{ and } n.$$

By well-ordering choose one with $N$ as small as possible. If $N > 1$, let $p$ be a prime divisor of $N$. Then $p$ divides every coefficient of $Nf = gh$, so by the lemma $p$ divides every coefficient of $g$, say (the case of $h$ is the same). Then $g/p$ is in $\mathbb{Z}[x]$, still of degree $m$, and $(N/p) f = (g/p) h$ is an equation of the same kind with a smaller multiplier, a contradiction. So $N = 1$ and $f = gh$ in $\mathbb{Z}[x]$. $\blacksquare$

On the example, $6f = (2x^2 - 4)(3x^2 + 3x + 3)$. The prime 2 divides 6 and every coefficient of $2x^2 - 4$, which leaves $3f = (x^2 - 2)(3x^2 + 3x + 3)$; the prime 3 divides every coefficient of the second factor, which leaves $f = (x^2 - 2)(x^2 + x + 1)$. This is Hungerford's Theorem 4.23; Judson (2026, Theorem 17.3.4) states the monic case under the same name.

Gauss's lemma turns the search for a factorization into a finite problem in integers, and the search can find a factorization as well as rule one out. Suppose the factors of the running example were not known in advance. The opening showed that $f(x)$ has no rational root, so it has no linear factor, and if it is reducible it is a product of two quadratics, by Gauss's lemma of two integer quadratics. Their leading coefficients multiply to 1, so both are 1 or both are $-1$, and changing the sign of both factors makes them monic:

$$x^4 + x^3 - x^2 - 2x - 2 = (x^2 + ax + b)(x^2 + cx + d), \qquad a, b, c, d \in \mathbb{Z}.$$

Comparing coefficients gives $bd = -2$ (constant term), $ad + bc = -2$ ($x$), $ac + b + d = -1$ ($x^2$) and $a + c = 1$ ($x^3$). The constant terms are a pair of integers with product $-2$, and since the two factors can be listed in either order, it is enough to try $(b, d) = (-2, 1)$ and $(b, d) = (2, -1)$. In the first case the coefficient of $x$ gives $a - 2c = -2$, which with $a + c = 1$ forces $c = 1$ and $a = 0$, and then $ac + b + d = 0 - 2 + 1 = -1$ as required. In the second case $-a + 2c = -2$ and $a + c = 1$ give $c = -\tfrac{1}{3}$, not an integer. So the search finds exactly one factorization of this form, $f(x) = (x^2 - 2)(x^2 + x + 1)$, and the script confirms both cases.

Eisenstein's criterion

Theorem (Eisenstein's criterion). Let $f(x) = a_n x^n + \cdots + a_1 x + a_0 \in \mathbb{Z}[x]$ with $n \ge 1$. Suppose there is a prime $p$ such that $p$ divides $a_0, a_1, \ldots, a_{n-1}$, $p$ does not divide $a_n$, and $p^2$ does not divide $a_0$. Then $f(x)$ is irreducible in $\mathbb{Q}[x]$.

The idea of the proof: modulo $p$, the polynomial collapses to a constant times $x^n$. Any factorization over $\mathbb{Z}$ would then reduce to powers of $x$ on both sides, which makes both constant terms multiples of $p$ and their product a multiple of $p^2$.

Proof. Suppose $f$ is reducible in $\mathbb{Q}[x]$. By Gauss's lemma, $f = gh$ with $g, h \in \mathbb{Z}[x]$ of degrees $m \ge 1$ and $l \ge 1$, $m + l = n$. Reduce modulo $p$. The hypotheses say $\bar f = \bar a_n x^n$ with $\bar a_n \neq 0$, so $\bar g\, \bar h = \bar a_n x^n$ in $\mathbb{Z}_p[x]$. The leading coefficients of $g$ and $h$ multiply to $a_n$, which $p$ does not divide, so neither is divisible by $p$, and $\deg \bar g = m$, $\deg \bar h = l$.

Now apply unique factorization in $\mathbb{Z}_p[x]$, whose coefficients form a field. The polynomial $\bar a_n x^n$ is the constant $\bar a_n$ times $n$ copies of the monic irreducible $x$. The monic irreducible factors of $\bar g$ and $\bar h$ together make up a factorization of $\bar a_n x^n$, so by uniqueness they are all equal to $x$, and $\bar g$ and $\bar h$ are constant multiples of $x^m$ and $x^l$. Since $m, l \ge 1$, both have constant term 0: $p$ divides the constant terms $b_0$ of $g$ and $c_0$ of $h$. Then $p^2$ divides $b_0 c_0 = a_0$, contrary to hypothesis. $\blacksquare$

The criterion is Hungerford's Theorem 4.24 and Judson's Theorem 17.3.7. The course text proves it by tracing the coefficients of $g$ and $h$ one at a time; the argument above lets unique factorization in $\mathbb{Z}_p[x]$ do that work. For example, the quintic

$$2x^5 + 9x^3 - 6x + 15$$

is irreducible in $\mathbb{Q}[x]$ with $p = 3$: the prime 3 divides $15, -6, 0, 9, 0$, it does not divide the leading coefficient 2, and $9$ does not divide 15. Its reduction modulo 3 is $2x^5$, as the proof requires. No root test could have shown this, since a quintic could factor as a quadratic times a cubic. With $p = 5$ the criterion shows that $x^n - 10$ is irreducible in $\mathbb{Q}[x]$ for every $n \ge 1$, so $\mathbb{Q}[x]$ has irreducible polynomials of every degree, unlike $\mathbb{R}[x]$ and $\mathbb{C}[x]$ below.

The criterion is a sufficient condition only. For the running example $f(x)$, the coefficient of $x^3$ is 1, which no prime divides, so no prime qualifies and the criterion is silent; that $f$ is reducible had to be found by other means. When no prime qualifies, the criterion decides nothing either way, and the next test is one of the alternatives.

Check your understanding. Eisenstein's criterion with $p = 5$ shows that $x^4 - 10$ is irreducible over $\mathbb{Q}$. Is its reduction modulo 5 irreducible in $\mathbb{Z}_5[x]$?

It is not: modulo 5 it is $x^4 = x \cdot x^3$ (script). That is no contradiction. Eisenstein's proof reduces modulo $p$ because the reduction is a power of $x$, whose factorizations are easy to list. The next test needs a prime for which the reduction is irreducible, so for degree 2 or more the two tests never use the same prime.

Reduction modulo a prime

Theorem. Let $f(x) = a_n x^n + \cdots + a_0 \in \mathbb{Z}[x]$ and let $p$ be a prime that does not divide $a_n$. If $\bar f(x)$ is irreducible in $\mathbb{Z}_p[x]$, then $f(x)$ is irreducible in $\mathbb{Q}[x]$.

The idea: a factorization over $\mathbb{Q}$ becomes, by Gauss's lemma, a factorization over $\mathbb{Z}$, and reducing it modulo $p$ keeps the degrees and gives a factorization over $\mathbb{Z}_p$.

Proof. Since $p \nmid a_n$, $\deg \bar f = \deg f$, and since $\bar f$ is irreducible, this degree is at least 1. Suppose $f$ is reducible in $\mathbb{Q}[x]$. By Gauss's lemma $f = gh$ in $\mathbb{Z}[x]$ with $\deg g$ and $\deg h$ both positive and less than $\deg f$. The leading coefficients of $g$ and $h$ multiply to $a_n$, so $p$ divides neither, and $\bar g$ and $\bar h$ have the same degrees as $g$ and $h$. Then $\bar f = \bar g\, \bar h$ is a product of two polynomials of lower degree in $\mathbb{Z}_p[x]$, contradicting its irreducibility. $\blacksquare$

This is Hungerford's Theorem 4.25. It converts a question over the infinite field $\mathbb{Q}$ into a finite question over $\mathbb{Z}_p$. Two examples:

  • $k(x) = x^4 + 3x^3 + 1$ reduces modulo 2 to $x^4 + x^3 + 1$, which has no root in $\mathbb{Z}_2$ (its values at 0 and 1 are both 1). A factorization into two quadratics over $\mathbb{Z}_2$ would have the form $(x^2 + ax + b)(x^2 + cx + d)$, since the only nonzero element of $\mathbb{Z}_2$ is 1. Then $bd = 1$ forces $b = d = 1$, and the coefficients of $x^3$ and of $x$ would be $a + c$ and $a + c$, which must equal 1 and 0. So $\bar k$ is irreducible in $\mathbb{Z}_2[x]$, and $k(x)$ is irreducible in $\mathbb{Q}[x]$.
  • $m(x) = x^5 - x - 1$ reduces modulo 3 to $x^5 + 2x + 2$. It has no root in $\mathbb{Z}_3$: for every $a \in \mathbb{Z}_3$, $a^3 = a$ by Fermat's little theorem, so $a^5 = a^3 a^2 = a^3 = a$ and $\bar m(a) = a - a - 1 = -1 \neq 0$. A reducible quintic has a factor of degree 1 or 2, and the script divides $\bar m$ by each of the nine monic quadratics in $\mathbb{Z}_3[x]$ and finds a nonzero remainder every time. So $\bar m$ is irreducible, and $m(x)$ is irreducible in $\mathbb{Q}[x]$.

The converse fails, and the choice of prime matters. Modulo 2, $m(x)$ becomes $x^5 + x + 1 = (x^2 + x + 1)(x^3 + x^2 + 1)$, and modulo 3, $k(x)$ becomes $x^4 + 1 = (x^2 + x + 2)(x^2 + 2x + 2)$. A factorization modulo $p$ proves nothing about $\mathbb{Q}$; only an irreducible reduction does.

Irreducibles over $\mathbb{Z}_p$

The reduction test is useful because irreducible polynomials over $\mathbb{Z}_p$ are plentiful. The script counts the monic irreducibles of each degree by trial division:

Degree $n$ 1 2 3 4 5 6 7 8
over $\mathbb{Z}_2$ 2 1 2 3 6 9 18 30
over $\mathbb{Z}_3$ 3 3 8 18 48 116 312 810
The number of monic irreducible polynomials of each degree over \mathbb{Z}_2 and \mathbb{Z}_3 (dots, counted by trial division), on a logarithmic scale, against p^n/n (lines). Notice that from degree 5 on, the counts sit just below the lines: roughly one monic polynomial of degree n in n is irreducible.
The number of monic irreducible polynomials of each degree over $\mathbb{Z}_2$ and $\mathbb{Z}_3$ (dots, counted by trial division), on a logarithmic scale, against $p^n/n$ (lines). Notice that from degree 5 on, the counts sit just below the lines: roughly one monic polynomial of degree $n$ in $n$ is irreducible.

There are $p^n$ monic polynomials of degree $n$ over $\mathbb{Z}_p$, and the counts track $p^n / n$ closely, so roughly one in $n$ of them is irreducible: 30 of the 256 monic polynomials of degree 8 over $\mathbb{Z}_2$, and 810 of the 6561 over $\mathbb{Z}_3$. In particular there are irreducible polynomials of every degree in the table. That holds for every degree and every prime, as a consequence of the existence of a field with $p^n$ elements (Judson, 2026, §22.1), and these polynomials are the raw material of the finite fields in the next unit.

Irreducibility over the real and complex numbers

Over $\mathbb{C}$ and $\mathbb{R}$ the question of irreducibility has a complete answer, but it rests on a theorem from outside algebra.

Theorem (fundamental theorem of algebra). Every nonconstant polynomial in $\mathbb{C}[x]$ has a root in $\mathbb{C}$.

The theorem is stated here without proof, as in the course text (Hungerford, 2014, Theorem 4.26). Judson (2026, Theorem 23.3.8) proves it with Galois theory. He remarks that even that algebraic proof relies on the completeness of the real numbers, through the facts that a real polynomial of odd degree has a real root and that positive reals have square roots. He credits the first proof to Gauss's doctoral thesis (Judson, 2026, §21.1).

Corollary. A polynomial is irreducible in $\mathbb{C}[x]$ if and only if it has degree 1. Every polynomial of degree $n \ge 1$ in $\mathbb{C}[x]$ factors as $c(x - z_1)(x - z_2) \cdots (x - z_n)$, uniquely up to the order of the factors.

Proof. Degree 1 polynomials are irreducible. A polynomial of degree at least 2 has a root by the fundamental theorem, so it is reducible by the root test. The factorization is the normal form of unique factorization, in which every monic irreducible is $x - z$. $\blacksquare$

For real polynomials one more fact is needed. Complex conjugation, $a + bi \mapsto a - bi$, respects sums and products and fixes every real number.

Lemma. If $f(x) \in \mathbb{R}[x]$ and $z \in \mathbb{C}$ is a root of $f(x)$, then so is its conjugate $\bar z$.

Proof. Write $f = \sum a_k x^k$ with real $a_k$. Then $f(\bar z) = \sum a_k \bar z^k = \overline{\sum a_k z^k} = \overline{f(z)} = \bar 0 = 0$, using that conjugation respects sums and products and fixes each $a_k$. $\blacksquare$

With the lemma, nonreal roots come in conjugate pairs, and each pair multiplies out to a real quadratic. So a real polynomial can always be split into pieces of degree 1 and 2.

Theorem. A polynomial is irreducible in $\mathbb{R}[x]$ if and only if it has degree 1, or it is a quadratic $ax^2 + bx + c$ with $b^2 - 4ac < 0$.

Proof. Degree 1 polynomials are irreducible. For a quadratic with $a \neq 0$, completing the square gives

$$ax^2 + bx + c = a\Big(x + \frac{b}{2a}\Big)^2 + \frac{4ac - b^2}{4a}.$$

When $b^2 - 4ac < 0$, the constant $(4ac - b^2)/4a$ is nonzero with the sign of $a$, and for real $x$ the first term is 0 or has the sign of $a$, so the sum is never 0. Being of degree 2 without real roots, the quadratic is irreducible. (When $b^2 - 4ac \ge 0$ the quadratic formula gives a real root, and the quadratic is reducible.)

Conversely, let $p(x)$ be irreducible in $\mathbb{R}[x]$ of degree at least 2. By the fundamental theorem it has a complex root $z$, which is not real, since a real root would give a linear factor. By the lemma, $\bar z \neq z$ is also a root. The polynomial

$$q(x) = (x - z)(x - \bar z) = x^2 - (z + \bar z)x + z\bar z$$

has real coefficients, since $z + \bar z$ is twice the real part of $z$ and $z \bar z = \lvert z \rvert^2$. Divide in $\mathbb{R}[x]$: $p = qs + r$ with $r = 0$ or $\deg r \le 1$. Evaluating at $z$ and at $\bar z$ gives $r(z) = r(\bar z) = 0$, so $r$, which has real coefficients and degree at most 1, has two distinct roots and must be 0. Hence $q \mid p$, and as $p$ is irreducible and $q$ is not a constant, $p$ is an associate of $q$: a quadratic without real roots, so with negative discriminant. $\blacksquare$

Corollary. Every polynomial of odd degree in $\mathbb{R}[x]$ has a real root.

Proof. Its irreducible factors have degree 1 or 2, and their degrees add to an odd number, so at least one has degree 1, and that factor has a real root. $\blacksquare$

These are Hungerford's Lemma 4.29, Theorem 4.30 and Corollary 4.31. The corollary can also be proved directly from calculus, by the intermediate value theorem, and the cubic $c(x)$ above shows it in action, with its sign change between $-\tfrac{5}{2}$ and $-1$.

For the running example, $x^2 + x + 1$ has discriminant $1 - 4 = -3 < 0$, so it is irreducible over $\mathbb{R}$, while $x^2 - 2$ has discriminant 8 and splits. Its complex roots are $\omega = -\tfrac{1}{2} + \tfrac{\sqrt{3}}{2}i$ and $\bar\omega$, a conjugate pair as the lemma requires. Collecting everything, including the reductions modulo several primes computed by the script:

Field Factorization of $f(x) = x^4 + x^3 - x^2 - 2x - 2$ into monic irreducibles
$\mathbb{Q}$ $(x^2 - 2)(x^2 + x + 1)$
$\mathbb{R}$ $(x - \sqrt{2})(x + \sqrt{2})(x^2 + x + 1)$
$\mathbb{C}$ $(x - \sqrt{2})(x + \sqrt{2})(x - \omega)(x - \bar\omega)$
$\mathbb{Z}_3$ $(x + 2)^2 (x^2 + 1)$
$\mathbb{Z}_7$ $(x + 3)^2 (x + 4)(x + 5)$
$\mathbb{Z}_{11}$ $(x^2 + 9)(x^2 + x + 1)$
$\mathbb{Z}_{13}$ $(x + 4)(x + 10)(x^2 + 11)$
$\mathbb{Z}_{17}$ $(x + 6)(x + 11)(x^2 + x + 1)$

Modulo a prime $p \ne 2, 3$, the factor $x^2 - 2$ splits exactly when 2 is a square modulo $p$, and since $4(x^2 + x + 1) = (2x + 1)^2 + 3$, the factor $x^2 + x + 1$ splits exactly when $-3$ is a square. The primes 11, 13 and 17 show three of the four combinations, and 7 shows the fourth, with both splitting and the root 4 shared, so that $x - 4 = x + 3$ appears twice. Modulo 3, $x^2 + x + 1 = (x - 1)^2$ is a square. Which primes give which pattern is a question for number theory, the law of quadratic reciprocity, beyond this course. The point for algebra is the first column: irreducibility belongs to a polynomial together with a field.

Where it leads

  • An irreducible polynomial $p(x)$ plays the part of a prime modulus. Congruence modulo $p(x)$ (Congruence Modulo a Polynomial) produces a field, just as congruence modulo a prime produces $\mathbb{Z}_p$, and the irreducibles over $\mathbb{Z}_p$ counted above give the finite fields with $p^n$ elements.
  • The irreducible $x^2 + 1$ over $\mathbb{Z}_3$ already appeared in disguise: the field with nine elements in integral domains and fields is $\mathbb{Z}_3[i]$, and $i$ is a root of $x^2 + 1$.
  • Euclid's lemma made "irreducible" and "prime" the same property in $F[x]$, as in $\mathbb{Z}$. In general rings they differ, and the distinction is taken up through ideals and principal ideal domains.

What we have learned

Over a field, the irreducible polynomials are the primes. They satisfy Euclid's lemma, and every nonconstant polynomial factors into them uniquely up to order and constant multiples. Roots are linear factors, so a polynomial of degree $n$ has at most $n$ roots in a field. Irreducibility depends on the field: roots decide it in degrees 2 and 3, four tests decide many cases over $\mathbb{Q}$, and over $\mathbb{R}$ and $\mathbb{C}$ the fundamental theorem of algebra decides all. The one quartic $f$ factors differently over each field in the table.

That completes the parallel with the first unit. The second unit went on from primes to congruence modulo $n$, and the classes modulo a prime formed a field. Can the same be done modulo an irreducible polynomial? The next unit begins with Congruence Modulo a Polynomial.

References

  • Hungerford, T. W. (2014). Abstract Algebra: An Introduction (3rd ed.), §§4.3 to 4.6. Brooks/Cole, Cengage Learning. The course text: irreducibles (Theorem 4.11), their characterization by products (Theorem 4.12, Corollary 4.13), unique factorization (Theorem 4.14), the remainder and factor theorems (Theorems 4.15 and 4.16), roots and irreducibility (Corollaries 4.17 to 4.20), the rational root test (Theorem 4.21), Gauss's lemma (Lemma 4.22, Theorem 4.23), Eisenstein's criterion (Theorem 4.24), reduction modulo $p$ (Theorem 4.25), and the real and complex cases (Theorem 4.26 to Corollary 4.31). record · 44 pages
  • Judson, T. W. (2026). Abstract Algebra: Theory and Applications (annual edition, August 2026). §17.2 (Corollaries 17.2.3 and 17.2.4 on roots), §17.3 (Gauss's lemma, Theorem 17.3.4; Eisenstein's criterion, Theorem 17.3.7), §21.1 (the fundamental theorem of algebra and Gauss's thesis), §22.1 (fields with $p^n$ elements), and §23.3.3 (a proof of the fundamental theorem of algebra, Theorem 23.3.8). Free online at judsonbooks.org. record · 44 pages