---
title: Irreducibility Criteria and Gröbner Bases
module: Factorization and Polynomial Rings
moduleNumber: 7
lessonNumber: 4
order: 704
summary: >
  Deciding whether a given polynomial is irreducible, and computing in
  multivariate polynomial rings. In one variable: the rational root test,
  reduction modulo a prime, and Eisenstein's criterion. In several variables,
  where division fails, a monomial order gives leading terms, a Gröbner basis
  restores a well-defined remainder, and Buchberger's algorithm computes it.
topics: [Factorization and Polynomial Rings]
sources:
  - book: Dummit & Foote
    ref: "Ch. 9 — Polynomial Rings; §9.4 Irreducibility Criteria, §9.5 Polynomial Rings over Fields II, §9.6 Polynomials in Several Variables and Gröbner Bases"
  - book: Judson
    ref: "Ch. 17 — Polynomials; §17.3 Irreducible Polynomials"
draft: false
---

Unique factorization,
[established for $R[x]$ when $R$ is a UFD](/abstract-algebra/factorization-and-polynomials/gauss-lemma-and-unique-factorization),
guarantees that a polynomial _has_ a factorization into irreducibles, but says
nothing about how to find it or whether a given polynomial is already
irreducible. Three criteria decide the one-variable case over $\mathbb{Q}$: the
rational root test, reduction modulo a prime, and Eisenstein's criterion. In
several variables $F[x_1, \dots, x_n]$ is no longer a PID and the division
algorithm is noncanonical; Gröbner bases repair the division, giving a computable
normal form and an ideal-membership test.

## Rational roots and low-degree factors

By Gauss's lemma it suffices to test irreducibility over $\mathbb{Q}$ by working
in $\mathbb{Z}[x]$. The first tool locates any linear factor.

> **Proposition (Rational root test).** Let $p(x) = a_n x^n + \cdots + a_1 x +
> a_0 \in \mathbb{Z}[x]$. If $\tfrac{r}{s} \in \mathbb{Q}$ in lowest terms is a
> root, then $r \mid a_0$ and $s \mid a_n$. In particular a monic integer
> polynomial with no integer root among the divisors of $a_0$ has no rational
> root at all.[^df94]

Substituting $r/s$ and clearing denominators gives $a_n r^n = -s(a_{n-1}r^{n-1} +
\cdots + a_0 s^{n-1})$, so $s \mid a_n r^n$; since $\gcd(r, s) = 1$, $s \mid
a_n$, and symmetrically $r \mid a_0$. Combined with the
[factor theorem](/abstract-algebra/factorization-and-polynomials/polynomial-rings-over-fields),
this settles degrees $2$ and $3$: such a polynomial is reducible over $\mathbb{Q}$
if and only if it has a rational root, and the candidates are the finitely many
$r/s$ above. For $x^3 - 3x - 1$ the only candidates are $\pm 1$, and neither is a
root, so it is irreducible in $\mathbb{Z}[x]$ and $\mathbb{Q}[x]$.

> **Worked example.** Factor $2x^3 - x^2 - 8x + 4$ over $\mathbb{Q}$. Any root
> $\tfrac{r}{s}$ in lowest terms has $r \mid 4$ and $s \mid 2$, giving candidates
> $\pm 1, \pm 2, \pm 4, \pm\tfrac{1}{2}$. Testing $x = 2$ gives
> $16 - 4 - 16 + 4 = 0$, so $(x - 2)$ divides the polynomial:
> $$
> 2x^3 - x^2 - 8x + 4 = (x - 2)(2x^2 + 3x - 2) = (x - 2)(2x - 1)(x + 2).
> $$
> All three factors are linear, so the polynomial is a product of three
> irreducibles in $\mathbb{Q}[x]$.

The test is silent above degree $3$: a quartic can be a product of two
irreducible quadratics, hence reducible with no linear factor and no rational
root. Two criteria reach the higher degrees.

## Reduction modulo a prime

Pushing a polynomial into $\mathbb{F}_p[x]$, where there are only finitely many
polynomials of each degree, can expose irreducibility.

> **Proposition (Reduction criterion).** Let $I$ be a proper ideal of a domain
> $R$ and $p(x)$ a monic polynomial in $R[x]$. If the image $\bar p$ in
> $(R/I)[x]$ cannot be factored into two polynomials of smaller degree, then
> $p(x)$ is irreducible in $R[x]$.[^df94]

A factorization $p = ab$ in $R[x]$ with $a, b$ monic and nonconstant reduces to a
factorization $\bar p = \bar a \bar b$ of the same degrees, so if none exists mod
$I$, none exists over $R$. For $R = \mathbb{Z}$, $I = (p)$, this reads: if a monic
$f \in \mathbb{Z}[x]$ stays irreducible modulo some prime $p$, it is irreducible
over $\mathbb{Z}$. Since $\mathbb{F}_p[x]$ has finitely many low-degree
polynomials, the reduced test is a finite check. For $x^2 + x + 1$, reduction mod
$2$ gives a polynomial with no root in $\mathbb{F}_2$ (values $1$ and $1$), hence
irreducible mod $2$, hence irreducible over $\mathbb{Z}$.

Two warnings. The criterion is one-directional: $x^2 + 1$ is irreducible over
$\mathbb{Z}$ (irreducible mod $3$) but reducible mod $2$ as $(x + 1)^2$, so
failing modulo one prime proves nothing. And it can miss irreducibility
entirely: $x^4 + 1$ is irreducible over $\mathbb{Z}$ but factors modulo _every_
prime.[^df94]

$$
% caption: Reduction modulo p sends a factorization over Z to one over the finite
% field; if no factorization survives in the small ring F_p[x], none existed
% upstairs.
\begin{tikzpicture}[scale=1.0, >=stealth, font=\footnotesize,
  box/.style={draw, minimum width=34mm, minimum height=9mm, align=center}]
\definecolor{acc}{HTML}{4A6FA5}
\node[box] (zx) at (0,1.2) {$f(x)$ in $\mathbb{Z}[x]$};
\node[box] (fx) at (0,-0.6) {$\bar f(x)$ in $\mathbb{F}_p[x]$};
\node[box, draw=acc, text=acc, thick] (irr) at (6,-0.6) {$\bar f$ has no proper factor};
\node[box, draw=acc, text=acc, thick] (con) at (6,1.2) {so $f$ is irreducible};
\draw[->, acc] (zx) -- (fx) node[midway, right, black] {reduce mod $p$};
\draw[->, acc] (fx) -- (irr) node[midway, above, black] {finite check};
\draw[->, acc] (irr) -- (con);
\end{tikzpicture}
$$

> **Worked example.** Show $x^4 + x + 1$ is irreducible over $\mathbb{Q}$ by
> reducing mod $2$. Over $\mathbb{F}_2$ it has no root ($0 \mapsto 1$,
> $1 \mapsto 1$), so no linear factor. The only irreducible quadratic over
> $\mathbb{F}_2$ is $x^2 + x + 1$, and
> $$
> (x^2 + x + 1)^2 = x^4 + x^2 + 1 \neq x^4 + x + 1,
> $$
> so there is no quadratic factor either. Thus $x^4 + x + 1$ is irreducible in
> $\mathbb{F}_2[x]$, hence irreducible in $\mathbb{Z}[x]$ and $\mathbb{Q}[x]$.

## Eisenstein's criterion

Eisenstein's criterion is a special case of reduction and among the most useful
tests in practice.

> **Proposition (Eisenstein's criterion).** Let $P$ be a prime ideal of a domain
> $R$ and $f(x) = x^n + a_{n-1}x^{n-1} + \cdots + a_1 x + a_0 \in R[x]$ with
> $n \geq 1$. If $a_{n-1}, \dots, a_1, a_0 \in P$ but $a_0 \notin P^2$, then
> $f(x)$ is irreducible in $R[x]$.[^df94]

For $R = \mathbb{Z}$ and $P = (p)$: if a prime $p$ divides every coefficient
except the leading one, and $p^2$ does not divide the constant term, then $f$ is
irreducible in $\mathbb{Z}[x]$ and $\mathbb{Q}[x]$. The proof reduces mod $P$ to
$\bar f = x^n$. A factorization $f = ab$ with $a, b$ nonconstant would reduce to
$x^n = \bar a \bar b$ in the domain $(R/P)[x]$, forcing both $\bar a$ and $\bar b$
to have zero constant term; then both constant terms of $a$ and $b$ lie in $P$,
so $a_0 \in P^2$, contradiction.

$$
% caption: Eisenstein's criterion as a checklist against a prime p: the leading
% coefficient escapes p, every lower coefficient is caught by p, and the constant
% term escapes p squared.
\begin{tikzpicture}[scale=1.0, >=stealth, font=\footnotesize,
  chk/.style={draw, minimum width=62mm, minimum height=9mm, align=left, inner xsep=4mm}]
\definecolor{acc}{HTML}{4A6FA5}
\node[chk] (c1) at (0,1.6) {$p$ does not divide the leading coefficient $a_n$};
\node[chk] (c2) at (0,0.4) {$p$ divides every non-leading coefficient};
\node[chk] (c3) at (0,-0.8) {$p^2$ does not divide the constant term $a_0$};
\node[chk, draw=acc, text=acc, thick] (out) at (0,-2.2) {all three hold: $f$ is irreducible};
\draw[->, acc] (c1) -- (c2);
\draw[->, acc] (c2) -- (c3);
\draw[->, acc] (c3) -- (out);
\end{tikzpicture}
$$

Eisenstein applies where it seems not to, after a substitution.

- **$n$th roots.** $x^n - p$ is Eisenstein at $p$, so $\sqrt[n]{p}$ is irrational
  for $n \geq 2$.
- **The cyclotomic polynomial.** $\Phi_p(x) = \tfrac{x^p - 1}{x - 1} = x^{p-1} +
  \cdots + x + 1$ is not directly Eisenstein, but $\Phi_p(x + 1) = x^{p-1} +
  \binom{p}{1}x^{p-2} + \cdots + p$ is, since $p \mid \binom{p}{k}$ for $0 < k <
  p$ while the constant term is exactly $p$. So $\Phi_p$ is irreducible over
  $\mathbb{Q}$, a fact the
  [cyclotomic fields lesson](/abstract-algebra/field-theory/separable-and-cyclotomic-extensions)
  needs.[^df94]

Judson notes the practical reading: Eisenstein is better at _constructing_
irreducible polynomials of any degree than at testing an arbitrary one, since a
random polynomial rarely has a prime dividing all but the top coefficient.[^ju173]

> **Worked example.** The fifth cyclotomic polynomial
> $\Phi_5(x) = x^4 + x^3 + x^2 + x + 1$ is Eisenstein at no prime, but its shift
> is. Substituting $x \mapsto x + 1$,
> $$
> \Phi_5(x + 1) = \frac{(x + 1)^5 - 1}{x} = x^4 + 5x^3 + 10x^2 + 10x + 5.
> $$
> Every non-leading coefficient is divisible by $5$, and the constant term $5$
> is not divisible by $25$, so Eisenstein at $5$ applies: $\Phi_5(x + 1)$ is
> irreducible, and a shift preserves irreducibility, so $\Phi_5$ is irreducible
> over $\mathbb{Q}$. The same expansion with $p \mid \binom{p}{k}$ for
> $0 < k < p$ shows $\Phi_p$ is irreducible for every prime $p$.

| Criterion | Applies to | Detects | Limitation |
| --- | --- | --- | --- |
| Rational root test | any degree | linear factors | blind to higher-degree factors |
| Degree $2$ / $3$ + roots | degree $\leq 3$ | full irreducibility | degree $\leq 3$ only |
| Reduction mod $p$ | monic $f$ | irreducibility if $\bar f$ is | may fail for every $p$ |
| Eisenstein at $p$ | $f$ fitting the pattern | full irreducibility | needs a suitable prime |

## Splitting a quotient by the CRT

One more consequence of factorization in $F[x]$ closes the one-variable theory.
If $g \in F[x]$ factors as $g = f_1^{n_1} \cdots f_k^{n_k}$ into distinct
irreducibles, the ideals $(f_i^{n_i})$ are pairwise comaximal (distinct
irreducibles are coprime in the PID $F[x]$), so the
[Chinese remainder theorem](/abstract-algebra/ring-theory/fractions-and-the-chinese-remainder-theorem)
gives

$$
F[x]/(g) \;\cong\; F[x]/(f_1^{n_1}) \times \cdots \times F[x]/(f_k^{n_k}).
$$

Each factor $F[x]/(f_i)$ with $f_i$ irreducible is a field, so this decomposition
splits a quotient ring into simpler pieces, the same statement that, over
$\mathbb{Z}$, decomposes $\mathbb{Z}/n\mathbb{Z}$ along the prime-power
factorization of $n$.[^df95]

## Several variables and monomial orders

For $n \geq 2$ the ring $F[x_1, \dots, x_n] = F[x_1, \dots, x_{n-1}][x_n]$ is a
UFD but not a PID, so there is no single generator and no Euclidean division.
Finiteness of generation still holds.

> **Theorem (Hilbert basis theorem).** If $R$ is Noetherian — every ideal
> finitely generated — then $R[x]$ is Noetherian. Hence every ideal of
> $F[x_1, \dots, x_n]$ is finitely generated.[^df96]

The proof collects the leading coefficients of an ideal $I \subseteq R[x]$ into
an ideal $L$ of $R$, which is finitely generated since $R$ is Noetherian; lifting
generators of $L$ and of the lower-degree leading-coefficient ideals back to $I$
produces a finite generating set. Induction on the number of variables, starting
from the field $F$, gives the corollary.

To speak of a "leading term" in several variables requires ordering the
monomials, since $x^2 y$ and $x y^3$ are otherwise incomparable.

> **Definition (Monomial order).** A **monomial order** is a total well-ordering
> $\geq$ on the monomials such that $m \geq 1$ for all $m$, and $m_1 \geq m_2$
> implies $m m_1 \geq m m_2$. The **lexicographic** order fixes $x_1 > x_2 >
> \cdots > x_n$ and compares exponent tuples left to right: the first coordinate
> where they differ decides.[^df96]

Fixing an order, the **leading term** $\mathrm{LT}(f)$ is the term of highest
monomial, and the **leading-term ideal** of $I$ is $\mathrm{LT}(I) = (\mathrm{LT}(f)
: f \in I)$. The leading term depends on the order: for $2xy + y^3$, lex with
$x > y$ makes $\mathrm{LT} = 2xy$, but $y > x$ makes it $y^3$. So the leading term
need not be the term of largest total degree.

$$
% caption: Lexicographic order on the exponent lattice with x above y: monomials
% are ranked by the x-exponent first, then the y-exponent, so columns further
% right always outrank everything to their left.
\begin{tikzpicture}[scale=0.9, >=stealth, font=\footnotesize]
\definecolor{acc}{HTML}{4A6FA5}
\draw[->, black] (0,0) -- (3.6,0) node[anchor=north] {exponent of $x$};
\draw[->, black] (0,0) -- (0,3.2) node[anchor=east, rotate=90, yshift=3mm] {exponent of $y$};
\foreach \x in {0,1,2,3} \foreach \y in {0,1,2}
  \fill[black] (\x,\y) circle (1.5pt);
\node[draw, acc, thick, circle, inner sep=1.4pt] at (3,0) {};
\node[acc, anchor=south] at (3,0.1) {$x^3$ (highest here)};
\node[anchor=west, black] at (0.1,2.55) {$y^2$};
\draw[acc, thick, ->] (0.3,2.6) .. controls (1.6,2.3) and (2.4,0.9) .. (2.9,0.15);
\node[acc, anchor=west] at (1.4,1.7) {larger $x$-degree wins};
\end{tikzpicture}
$$

## General polynomial division and its failure

With leading terms in hand, one-variable division extends to division by several
polynomials $g_1, \dots, g_m$ at once.

```algorithm
caption: $\textsc{Divide}(f, g_1, \dots, g_m)$ — general polynomial division
set quotients $q_1, \dots, q_m \gets 0$ and remainder $r \gets 0$
while $f \neq 0$ do
  if $\mathrm{LT}(g_i) \mid \mathrm{LT}(f)$ for some least $i$ then
    let $a = \mathrm{LT}(f) / \mathrm{LT}(g_i)$
    $q_i \gets q_i + a$;  $f \gets f - a\, g_i$   // cancel the leading term
  else
    $r \gets r + \mathrm{LT}(f)$;  $f \gets f - \mathrm{LT}(f)$   // move it to the remainder
return $q_1, \dots, q_m$ and $r$ with $f = \sum q_i g_i + r$
```

The `else` branch is new: in one variable division stops when the divisor's
leading term stops dividing, but here a lower term of $f$ might still be
divisible, so the leading term is set aside and the process continues. The output
satisfies $f = q_1 g_1 + \cdots + q_m g_m + r$ with no term of $r$ divisible by
any $\mathrm{LT}(g_i)$.

The trouble is that the answer depends on the _order_ of the divisors, so a zero
remainder is not a reliable test for membership in $(g_1, \dots, g_m)$. Take
$f = x^2 + x - y^2 + y$ with lex $x > y$. Dividing by $g_1 = xy + 1$ then $g_2 =
x + y$ leaves remainder $-y^2 + 1 \neq 0$; dividing by $g_2$ first leaves
remainder $0$. Both are legal outputs, yet $f$ _is_ in the ideal. The leading
terms of the generators simply fail to generate $\mathrm{LT}(I)$: the combination
$y g_1 - x g_2$ has leading term unaccounted for.[^df96]

## Gröbner bases and Buchberger's algorithm

The fix is to choose generators whose leading terms already generate all leading
terms of the ideal.

> **Definition (Gröbner basis).** A finite generating set $\{g_1, \dots, g_m\}$
> of an ideal $I \subseteq F[x_1, \dots, x_n]$ is a **Gröbner basis** (for the
> fixed order) if $\mathrm{LT}(I) = (\mathrm{LT}(g_1), \dots,
> \mathrm{LT}(g_m))$.[^df96]

Against a Gröbner basis, general division becomes canonical.

> **Theorem.** If $\{g_1, \dots, g_m\}$ is a Gröbner basis for $I$, every $f$ has
> a **unique** remainder $r$ under division, independent of divisor order, and
> $f \in I$ if and only if $r = 0$. The remainder is a canonical representative
> of the coset $f + I$ in $F[x_1, \dots, x_n]/I$.[^df96]

Uniqueness follows because a difference of two remainders lies in $I$, so its
leading term is divisible by some $\mathrm{LT}(g_i)$ — impossible unless the
difference is zero, since remainders have no such divisible terms. Gröbner bases
exist for every ideal, because $\mathrm{LT}(I)$ is a monomial ideal and Hilbert's
theorem makes it finitely generated by leading terms of finitely many ideal
elements.

What obstructs a generating set from being a Gröbner basis is the
cancellation of leading terms, packaged as the **$S$-polynomial**. For $f_i, f_j$
with monic least common multiple $M$ of $\mathrm{LT}(f_i)$ and $\mathrm{LT}(f_j)$,

$$
S(f_i, f_j) = \frac{M}{\mathrm{LT}(f_i)}\, f_i - \frac{M}{\mathrm{LT}(f_j)}\, f_j,
$$

built precisely to cancel the two leading terms. These account for every such
cancellation.

> **Theorem (Buchberger's criterion).** $\{g_1, \dots, g_m\}$ is a Gröbner basis
> for $I = (g_1, \dots, g_m)$ if and only if the remainder of every
> $S(g_i, g_j)$ under division by $g_1, \dots, g_m$ is $0$.[^df96]

The criterion is a terminating algorithm: whenever some $S$-polynomial has
nonzero remainder $r$, that $r$ is a genuinely new element of $I$ whose leading
term was missing, so append it and repeat.

```algorithm
caption: $\textsc{Buchberger}(g_1, \dots, g_m)$ — compute a Gröbner basis
$G \gets \{g_1, \dots, g_m\}$
repeat
  for each pair $g_i, g_j$ in $G$ do
    $r \gets$ remainder of $S(g_i, g_j)$ divided by $G$
    if $r \neq 0$ then add $r$ to $G$
until every pair gives remainder $0$
return $G$
```

Termination holds because each appended $r$ enlarges the monomial ideal
$\mathrm{LT}(G)$, and Hilbert's theorem forbids an infinite strictly ascending
chain of such ideals. Deleting any $g_j$ whose leading term is divisible by
another, and scaling leading terms to be monic, yields a **minimal** Gröbner
basis; reducing further so no term of one basis element is divisible by another's
leading term yields the **reduced** Gröbner basis, which is unique for the fixed
order.[^df96]

$$
% caption: Buchberger's loop: form the S-polynomial of a pair to cancel leading
% terms, divide by the current basis, and either the remainder is zero or it is a
% new generator to append; the leading-term ideal grows and the loop halts.
\begin{tikzpicture}[scale=1.0, >=stealth, font=\footnotesize,
  box/.style={draw, minimum width=30mm, minimum height=9mm, align=center}]
\definecolor{acc}{HTML}{4A6FA5}
\node[box] (pair) at (0,2.4) {pick a pair $g_i$, $g_j$};
\node[box] (s) at (0,1.0) {form the $S$-polynomial};
\node[box] (div) at (0,-0.4) {divide by $G$, get $r$};
\node[box, draw=acc, text=acc] (add) at (4.4,-0.4) {append $r$ to $G$};
\node[box, draw=acc, text=acc, thick] (done) at (0,-1.8) {all pairs give $r = 0$};
\draw[->, acc] (pair) -- (s);
\draw[->, acc] (s) -- (div);
\draw[->, acc] (div) -- (add) node[midway, above, black] {$r \neq 0$};
\draw[->, acc] (add) |- (pair);
\draw[->, acc] (div) -- (done) node[midway, right, black] {$r = 0$ for all};
\end{tikzpicture}
$$

For the ideal $I = (x^3 y - x y^2 + 1,\ x^2 y^2 - y^3 - 1)$ with lex $x > y$, one
$S$-polynomial is $y f_1 - x f_2 = x + y$, whose leading term $x$ is new;
appending it and iterating terminates at the reduced basis $\{x + y,\ y^4 - y^3 -
1\}$. This is a far simpler description of the same ideal, and it exposes the
computation as a decision procedure: $f \in I$ reduces to a single division with
remainder. The same normal-form computation underlies ideal membership, elimination,
and the ideal–variety dictionary of
[algebraic geometry](/abstract-algebra/capstone/commutative-algebra-and-algebraic-geometry).[^df96]

[^df94]: **Dummit & Foote**, _Abstract Algebra_, §9.4 — Irreducibility Criteria: the rational root test, reducibility of degree-2 and degree-3 polynomials by roots, reduction modulo an ideal, and Eisenstein's criterion with the cyclotomic and $n$th-root applications.
[^df95]: **Dummit & Foote**, _Abstract Algebra_, §9.5 — Polynomial Rings over Fields II: the Chinese remainder decomposition of $F[x]/(g)$ along the irreducible factorization of $g$.
[^df96]: **Dummit & Foote**, _Abstract Algebra_, §9.6 — Polynomials in Several Variables over a Field and Gröbner Bases: the Hilbert basis theorem, monomial orders and leading-term ideals, general polynomial division, the Gröbner-basis definition and unique-remainder theorem, $S$-polynomials, Buchberger's criterion and algorithm, and reduced Gröbner bases.
[^ju173]: **Judson**, _Abstract Algebra: Theory and Applications_, §17.3 — Irreducible Polynomials: the rational root corollary, Eisenstein's criterion, and its role in constructing irreducible polynomials of arbitrary degree.