Eisenstein's Irreducibility Criterion

Theorem: Let

\[ f(x) = a_0 + a_1 x + ... + a_n x^n \]

be a polynomial with integer coefficients. Suppose a prime \(p\) divides each of \(a_0, a_1, ..., a_{n-1}\) (every coefficient except the leading coefficient), and that \(p^2\) does not divide \(a_0\). Then \(p(x)\) has no factors with integer coefficients.

Proof: Suppose \(f = g h\) for polynomials \(g, h\) with integer coefficients. Look at this factorization modulo \(p\): we get \(f(x) = a_n x^n\), so \(g(x) = b_d x^d\), \(h(x) = c_e x^e\) for some constants \(b_d, c_e\) and for some integers \(d, e\) with \(d e = n\). This implies the constant term of \(g(x)\) is a multiple of \(p\), and similarly for the constant term of \(h(x)\), hence \(p^2\) divides the constant term of \(f(x)\), a contradiction.∎

Gauss' Lemma

We usually combine Eisenstein’s criterion with the following theorem for a stronger statement. (The name "Gauss' Lemma" has been given to several results in different areas of mathematics, including the following.)

Theorem: Let \(f \in \mathbb{Z}[x]\). Then \(f\) is irreducible over \(\mathbb{Z}[x]\) if and only if \(f\) is irreducible over \(\mathbb{Q}[x]\).

(In other words, Let \(f(x)\) be a polynomial with integer coefficients. If \(f(x)\) has no factors with integer coefficients, then \(f(x)\) has no factors with rational coefficients.)

Proof: Let \(f(x) = g(x)h(x)\) be a factorization of \(f\) into polynomials with rational coefficients. Then for some rational \(a\) the polynomial \(a g(x)\) has integer coefficients with no common factor. Similary we can find a rational \(b\) so that \(b h(x)\) has the same properties. (Take the lcm of the denominators of the coefficients in each case, and then divide by any common factors.)

Suppose a prime \(p\) divides \(a b\). Since

\[ a b f(x) = (a g(x))(b h(x)) \]

becomes \( 0 = (a g(x)) (b h(x))\) modulo \(p\), we see \(a g(x)\) or \(b h(x)\) is the zero polynomial modulo \(p\). (If not, then let the term of highest degree in \(a g(x)\) be \(m x^r\), and the term of highest degree in \(b h(x)\) be \(n x^s\). Then the product contains the term \(m n x^{r+s} \ne 0 \pmod {p}\), a contradiction.)

In other words, \(p\) divides each coefficient of \(a g(x)\) or \(b h(x)\), a contradiction. Hence \(a b = 1\) and we have a factorization over the integers.∎

Example: Let \(p\) be a prime. Consider the polynomial

\[ f(x) = 1 + x + ... + x^{p-1} . \]

We cannot yet apply the criterion, so make the variable subsitution \(x = y + 1\). Then we have

\[ g(y) = 1 + (y+1) + ... + (y+1)^{p-1} . \]

Note \(f(x)\) is irreducible if and only if \(g(y)\) is irreducible.

The coefficient of \(y^k\) in \(g(y)\) is

\[ \sum_{m=k}^{p-1} {\binom{p-1}{k}} = {\binom{p}{k+1}} . \]

The last equality can be shown via repeated applications of Pascal’s identity:

\[ {\binom{n+1}{k}} = {\binom{n}{k}} + {\binom{n}{k-1}} . \]

Alternatively, use the fact

\[ g(y) = \frac{(y+1)^p - 1}{(y+1) - 1} \]

Thus \(p\) divides each coefficient except the leading coefficient, and \(p^2\) does not divide the constant term \(p\), hence \(f(x)\) is irreducible over the rationals.

Ben Lynn blynn@cs.stanford.edu 💡