Irreducibility and factorization (Eisenstein, Gauss’s lemma)

Irreducible polynomials play the role in \(F[x]\) that primes play in \(\mathbb{Z}\). Every polynomial over a field factors into irreducibles, uniquely up to order and constant factors, and an irreducible polynomial \(p(x)\) generates a maximal ideal, so that \(F[x]/(p(x))\) is a field. Deciding irreducibility is therefore a practical question with large consequences. This lesson collects the standard tests: degree arguments with roots, the rational root test, reduction modulo a prime, Eisenstein's criterion, and Gauss's lemma, which links factorization over \(\mathbb{Z}\) to factorization over \(\mathbb{Q}\).

Irreducible polynomials

Definition. Let \(F\) be a field. A nonconstant polynomial \(f \in F[x]\) is irreducible over \(F\) if it cannot be written as \(f = gh\) with \(g, h \in F[x]\) both of smaller degree. Otherwise it is reducible.

Irreducibility depends on the field. \(x^2 - 2\) is irreducible over \(\mathbb{Q}\) but factors as \((x - \sqrt 2)(x + \sqrt 2)\) over \(\mathbb{R}\). \(x^2 + 1\) is irreducible over \(\mathbb{R}\) but factors as \((x - i)(x + i)\) over \(\mathbb{C}\), and as \((x + 1)^2\) over \(\mathbb{Z}_2\). Every polynomial of degree 1 is irreducible. Over \(\mathbb{C}\), by the fundamental theorem of algebra, the irreducibles are exactly the linear polynomials; over \(\mathbb{R}\) they are the linear polynomials and the quadratics with negative discriminant.

Theorem. Over a field, a polynomial of degree 2 or 3 is irreducible if and only if it has no root in the field.

Proof: if \(f = gh\) with both factors of smaller degree and \(\deg f \in \{2, 3\}\), one factor has degree 1, say \(ax + b\), and then \(-b/a\) is a root. Conversely a root \(c\) gives the factor \(x - c\). For degree 4 the test is not enough: \((x^2 + 1)^2\) and \(x^4 + 4 = (x^2 + 2x + 2)(x^2 - 2x + 2)\) have no rational roots but are reducible.

Theorem. If \(p(x)\) is irreducible over \(F\), then \((p(x))\) is a maximal ideal of \(F[x]\) and \(F[x]/(p(x))\) is a field.

Proof: suppose \((p) \subseteq J\) for an ideal \(J\). By lesson 6, \(J = (g)\), and \(p = gh\) for some \(h\). Since \(p\) is irreducible, \(g\) is a constant (so \(J = F[x]\)) or \(h\) is a constant (so \(J = (p)\)).

The rational root test

Theorem. If \(f = a_nx^n + \cdots + a_0 \in \mathbb{Z}[x]\) has a rational root \(r/s\) in lowest terms, then \(r \mid a_0\) and \(s \mid a_n\).

Proof: multiply \(f(r/s) = 0\) by \(s^n\): \(a_nr^n + a_{n-1}r^{n-1}s + \cdots + a_0s^n = 0\). Every term except \(a_0s^n\) is a multiple of \(r\), so \(r \mid a_0s^n\), and since \(\gcd(r, s) = 1\), \(r \mid a_0\). Similarly every term except \(a_nr^n\) is a multiple of \(s\), so \(s \mid a_n\).

Example: \(2x^3 - x^2 + 4x - 2\) can only have rational roots among \(\pm 1, \pm 2, \pm \frac12\). Trying them, \(\frac12\) works, giving \((2x - 1)(x^2 + 2)\). And \(x^3 - 3x - 1\), whose only candidates are \(\pm 1\), with values \(-3\) and \(1\), is irreducible over \(\mathbb{Q}\). This cubic returns in lesson 10, where it shows that the angle of \(60^\circ\) cannot be trisected.

Gauss's lemma

A polynomial in \(\mathbb{Z}[x]\) is primitive if the gcd of its coefficients is 1. Gauss proved in the Disquisitiones Arithmeticae of 1801 that the product of primitive polynomials is primitive. The consequence that matters is that factoring over \(\mathbb{Q}\) is no more powerful than factoring over \(\mathbb{Z}\).

Lemma (Gauss). The product of two primitive polynomials is primitive.

Proof: suppose \(f\) and \(g\) are primitive but a prime \(p\) divides every coefficient of \(fg\). Reduce modulo \(p\): \(\bar f \bar g = \overline{fg} = 0\) in \(\mathbb{Z}_p[x]\). But \(\mathbb{Z}_p[x]\) is an integral domain, so \(\bar f = 0\) or \(\bar g = 0\), meaning \(p\) divides every coefficient of \(f\) or of \(g\), a contradiction.

Theorem. If \(f \in \mathbb{Z}[x]\) factors over \(\mathbb{Q}\) as a product of polynomials of degrees \(m\) and \(n\), then it factors over \(\mathbb{Z}\) as a product of polynomials of the same degrees.

Proof: write \(f = gh\) with \(g, h \in \mathbb{Q}[x]\). Clearing denominators and extracting contents, \(g = \frac{a}{b}g_0\) and \(h = \frac{c}{d}h_0\) with \(g_0, h_0\) primitive in \(\mathbb{Z}[x]\). Then \(bd \cdot f = ac \cdot g_0h_0\). By Gauss's lemma \(g_0h_0\) is primitive, so the content of the right side is \(|ac|\), while the content of the left side is \(bd\) times the content of \(f\). Hence \(ac/bd\) is an integer, and \(f = \frac{ac}{bd}g_0 \cdot h_0\) is a factorization in \(\mathbb{Z}[x]\).

Reduction modulo p

Theorem. Let \(f \in \mathbb{Z}[x]\) and let \(p\) be a prime not dividing the leading coefficient of \(f\). If the reduction \(\bar f \in \mathbb{Z}_p[x]\) is irreducible over \(\mathbb{Z}_p\) and has the same degree as \(f\), then \(f\) is irreducible over \(\mathbb{Q}\).

Proof: a factorization \(f = gh\) over \(\mathbb{Z}\) into factors of smaller degree, which exists by Gauss's lemma if \(f\) is reducible over \(\mathbb{Q}\), reduces to \(\bar f = \bar g \bar h\). The leading coefficients of \(g, h\) are not divisible by \(p\), so \(\bar g, \bar h\) keep their degrees, and \(\bar f\) would be reducible.

Example: \(f = x^3 + 6x^2 + 3x + 13\) reduces modulo 2 to \(x^3 + x + 1\), which has no root in \(\mathbb{Z}_2\) (values 1 and 1), hence is irreducible there. So \(f\) is irreducible over \(\mathbb{Q}\). The converse fails badly: \(x^4 + 1\) is irreducible over \(\mathbb{Q}\) but reducible modulo every prime, as lesson 6 showed for \(p = 5\).

Eisenstein's criterion

Theorem (Eisenstein's criterion). Let \(f = a_nx^n + \cdots + a_1x + a_0 \in \mathbb{Z}[x]\). If there is a prime \(p\) with \(p \nmid a_n\), \(p \mid a_i\) for all \(i < n\), and \(p^2 \nmid a_0\), then \(f\) is irreducible over \(\mathbb{Q}\).

Proof: suppose \(f = gh\) in \(\mathbb{Z}[x]\) with \(\deg g, \deg h \ge 1\). Reducing modulo \(p\), \(\bar f = \bar a_nx^n\), so \(\bar g\bar h = \bar a_nx^n\). Since \(\mathbb{Z}_p[x]\) has unique factorization and \(x\) is irreducible, \(\bar g = bx^k\) and \(\bar h = cx^{n-k}\) with \(k, n - k \ge 1\) (degrees are kept because \(p \nmid a_n\)). Then the constant terms of \(g\) and \(h\) are both divisible by \(p\), so \(p^2\) divides their product \(a_0\), a contradiction.

Gotthold Eisenstein published the criterion in 1850; Theodor Schönemann had found it four years earlier, and it is sometimes called the Schönemann–Eisenstein criterion. It shows at once that \(x^n - 2\) is irreducible over \(\mathbb{Q}\) for every \(n\), so there are irreducible polynomials of every degree over \(\mathbb{Q}\). A substitution extends its reach: \(f(x)\) is irreducible exactly when \(f(x + 1)\) is.

The most famous application is the cyclotomic polynomial \(\Phi_p(x) = \frac{x^p - 1}{x - 1} = x^{p-1} + x^{p-2} + \cdots + 1\) for prime \(p\). Eisenstein does not apply directly, but \(\Phi_p(x + 1) = \frac{(x + 1)^p - 1}{x} = x^{p-1} + \binom{p}{1}x^{p-2} + \cdots + \binom{p}{p-1}\), whose non-leading coefficients are divisible by \(p\) and whose constant term is \(p\), not divisible by \(p^2\). So \(\Phi_p\) is irreducible. This is the fact Gauss needed to analyse the regular \(p\)-gon, and it returns in lesson 10.

Testing irreducibility by computer

Over \(\mathbb{Z}_p\) irreducibility can be decided by brute force: a polynomial of degree \(n\) is reducible exactly when it has a monic factor of degree between 1 and \(n/2\). The program checks all monic polynomials of small degree over \(\mathbb{Z}_2\) and \(\mathbb{Z}_3\), counts the irreducible ones, applies the rational root test and Eisenstein's criterion to a few integer polynomials, and confirms the factorizations of \(x^4 + 1\) modulo small primes.

from itertools import product
from fractions import Fraction as Fr
from math import gcd

def pmod(f, g, p):
    f = f[:]
    inv = pow(g[-1], -1, p)
    while len(f) >= len(g) and any(f):
        k = len(f) - len(g)
        c = f[-1] * inv % p
        for i, gi in enumerate(g):
            f[i + k] = (f[i + k] - c * gi) % p
        while f and f[-1] == 0:
            f.pop()
    return f

def monic(deg, p):
    for low in product(range(p), repeat=deg):
        yield list(low) + [1]

def irreducible(f, p):
    n = len(f) - 1
    return all(pmod(f, g, p) for d in range(1, n // 2 + 1) for g in monic(d, p))

for p in (2, 3):
    counts = [sum(irreducible(f, p) for f in monic(n, p)) for n in range(1, 5)]
    print(f"irreducible monic of degree 1..4 over Z_{p}:", counts)
print("over Z_2, degree 3:", [f for f in monic(3, 2) if irreducible(f, 2)])

def rational_roots(f):
    a0, an = f[0], f[-1]
    divs = lambda m: [d for d in range(1, abs(m) + 1) if m % d == 0]
    cands = {Fr(s * r, q) for r in divs(a0) for q in divs(an) for s in (1, -1)}
    return [str(c) for c in sorted(c for c in cands if sum(a * c**i for i, a in enumerate(f)) == 0)]

print("rational roots of 2x^3 - x^2 + 4x - 2:", rational_roots([-2, 4, -1, 2]))
print("rational roots of x^3 - 3x - 1:", rational_roots([-1, -3, 0, 1]))

def eisenstein(f):
    primes = [q for q in range(2, 100) if all(q % d for d in range(2, q))]
    return [p for p in primes if f[-1] % p and all(a % p == 0 for a in f[:-1])
            and f[0] % (p * p)]

print("Eisenstein primes for x^5 + 5x^4 + 10x^3 + 10x^2 + 5x + 5:", eisenstein([5, 5, 10, 10, 5, 1]))
print("Eisenstein primes for x^4 + 10x + 6:", eisenstein([6, 10, 0, 0, 1]))
print("Eisenstein primes for x^4 + 1:", eisenstein([1, 0, 0, 0, 1]))
print("x^4 + 1 irreducible mod p for p = 2, 3, 5, 7:",
      [irreducible([1, 0, 0, 0, 1], p) for p in (2, 3, 5, 7)])

irreducible monic of degree 1..4 over Z_2: [2, 1, 2, 3]
irreducible monic of degree 1..4 over Z_3: [3, 3, 8, 18]
over Z_2, degree 3: [[1, 0, 1, 1], [1, 1, 0, 1]]
rational roots of 2x^3 - x^2 + 4x - 2: ['1/2']
rational roots of x^3 - 3x - 1: []
Eisenstein primes for x^5 + 5x^4 + 10x^3 + 10x^2 + 5x + 5: [5]
Eisenstein primes for x^4 + 10x + 6: [2]
Eisenstein primes for x^4 + 1: []
x^4 + 1 irreducible mod p for p = 2, 3, 5, 7: [False, False, False, False]

Over \(\mathbb{Z}_2\) there are 2, 1, 2 and 3 irreducible monic polynomials of degrees 1 to 4. The two cubics are \(x^3 + x + 1\) and \(x^3 + x^2 + 1\), printed as coefficient lists constant term first; lesson 11 uses the first to build the field with 8 elements. Over \(\mathbb{Z}_3\) the counts are 3, 3, 8 and 18. There is an exact formula, due to Gauss: the number of monic irreducibles of degree \(n\) over \(\mathbb{Z}_p\) is \(\frac1n\sum_{d \mid n}\mu(d)p^{n/d}\), where \(\mu\) is the Möbius function. For \(p = 3\), \(n = 4\) it gives \(\frac14(81 - 9) = 18\). Eisenstein's criterion works for \(x^4 + 10x + 6\) with \(p = 2\) and says nothing about \(x^4 + 1\), which is nevertheless irreducible over \(\mathbb{Q}\) though reducible modulo 2, 3, 5 and 7.