Irreducibility Criteria and Gröbner Bases

Unique factorization, established for $R [x]$ when $R$ is a UFD, 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 $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 $Q$ by working in $Z [x]$ . The first tool locates any linear factor.

Substituting $r / s$ and clearing denominators gives $a_{n} r^{n} = - s (a_{n - 1} r^{n - 1} + \dots + a_{0} s^{n - 1})$ , so $s ∣ a_{n} r^{n}$ ; since $gcd (r, s) = 1$ , $s ∣ a_{n}$ , and symmetrically $r ∣ a_{0}$ . Combined with the factor theorem, this settles degrees $2$ and $3$ : such a polynomial is reducible over $Q$ if and only if it has a rational root, and the candidates are the finitely many $r / s$ above. For $x^{3} - 3 x - 1$ the only candidates are $\pm 1$ , and neither is a root, so it is irreducible in $Z [x]$ and $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 $F_{p} [x]$ , where there are only finitely many polynomials of each degree, can expose irreducibility.

A factorization $p = ab$ in $R [x]$ with $a, b$ monic and nonconstant reduces to a factorization $\overset{p}{ˉ} = \overset{a}{ˉ} \overset{ˉ}{b}$ of the same degrees, so if none exists mod $I$ , none exists over $R$ . For $R = Z$ , $I = (p)$ , this reads: if a monic $f \in Z [x]$ stays irreducible modulo some prime $p$ , it is irreducible over $Z$ . Since $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 $F_{2}$ (values $1$ and $1$ ), hence irreducible mod $2$ , hence irreducible over $Z$ .

Two warnings. The criterion is one-directional: $x^{2} + 1$ is irreducible over $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 $Z$ but factors modulo every prime.¹

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.

Eisenstein's criterion

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

For $R = 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 $Z [x]$ and $Q [x]$ . The proof reduces mod $P$ to $\overset{ˉ}{f} = x^{n}$ . A factorization $f = ab$ with $a, b$ nonconstant would reduce to $x^{n} = \overset{a}{ˉ} \overset{ˉ}{b}$ in the domain $(R / P) [x]$ , forcing both $\overset{a}{ˉ}$ and $\overset{ˉ}{b}$ to have zero constant term; then both constant terms of $a$ and $b$ lie in $P$ , so $a_{0} \in P^{2}$ , contradiction.

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.

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

$n$ th roots. $x^{n} - p$ is Eisenstein at $p$ , so $n p$ is irrational for $n \geq 2$ .
The cyclotomic polynomial. $Φ_{p} (x) = \frac{x ^{p} - 1}{x - 1} = x^{p - 1} + \dots + x + 1$ is not directly Eisenstein, but $Φ_{p} (x + 1) = x^{p - 1} + (1 p) x^{p - 2} + \dots + p$ is, since $p ∣ (k p)$ for $0 < k < p$ while the constant term is exactly $p$ . So $Φ_{p}$ is irreducible over $Q$ , a fact the cyclotomic fields lesson needs.¹

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.²

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 $\overset{ˉ}{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}} \dots 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 gives

F [x] / (g) ≅ F [x] / (f_{1}^{n_{1}}) \times \dots \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 $Z$ , decomposes $Z / n Z$ along the prime-power factorization of $n$ .³

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.

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.

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

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.

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:

\textsc{Divide}(f, g_1, \dots, g_m)

— general polynomial division

1
set quotients $q_1, \dots, q_m \gets 0$ and remainder $r \gets 0$
2
while $f \neq 0$ do
3
if $\mathrm{LT}(g_i) \mid \mathrm{LT}(f)$ for some least $i$ then
4
let $a = \mathrm{LT}(f) / \mathrm{LT}(g_i)$
5
$q_i \gets q_i + a$ ; $f \gets f - a\, g_i$
cancel the leading term
6
else
7
$r \gets r + \mathrm{LT}(f)$ ; $f \gets f - \mathrm{LT}(f)$
move it to the remainder
8
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} + \dots + q_{m} g_{m} + r$ with no term of $r$ divisible by any $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} = x y + 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 $LT (I)$ : the combination $y g_{1} - x g_{2}$ has leading term unaccounted for.⁴

Gröbner bases and Buchberger's algorithm

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

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

Uniqueness follows because a difference of two remainders lies in $I$ , so its leading term is divisible by some $LT (g_{i})$ — impossible unless the difference is zero, since remainders have no such divisible terms. Gröbner bases exist for every ideal, because $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 $LT (f_{i})$ and $LT (f_{j})$ ,

S (f_{i}, f_{j}) = \frac{M}{LT ( f _{i} )} f_{i} - \frac{M}{LT ( f _{j} )} f_{j},

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

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:

\textsc{Buchberger}(g_1, \dots, g_m)

— compute a Gröbner basis

1
$G \gets \{g_1, \dots, g_m\}$
2
repeat
3
for each pair $g_i, g_j$ in $G$ do
4
$r \gets$ remainder of $S(g_i, g_j)$ divided by $G$
5
if $r \neq 0$ then add $r$ to $G$
6
until every pair gives remainder $0$
7
return $G$

Termination holds because each appended $r$ enlarges the monomial ideal $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.⁴

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.

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.⁴

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. ↩ ↩² ↩³ ↩⁴ ↩⁵
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. ↩
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$ . ↩
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. ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶ ↩⁷ ↩⁸