# 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 $$f(x)$$ has no factor with integer coefficients.

Proof: Suppose $$f = g h$$. Look at this factorization modulo $$p$$.

It turns out $$\mathbb{F}_p[x]$$ is a unique factorization domain. Modulo $$p$$, since $$f = a_n x^n$$, we find $$g = b x^d$$ and $$h = c x^e$$ for some $$b, c, d + e = n$$.

In other words, $$p$$ must divide every non-leading coefficient of $$g$$ and $$h$$. In particular, $$p$$ divides constant terms of $$g$$ and $$h$$, hence $$p^2$$ must divide their product, that is, the constant term of $$f$$.∎

We can prove the theorem without introducing UFDs. As above, modulo $$p$$ we have $$f = a_n x^n$$, so $$f(0) = 0$$, thus $$g(0) h(0) = 0$$ modulo $$p$$. Then at least one of $$g(0)$$ and $$h(0)$$ is 0. Without loss of generality $$g(0) = 0$$, so $$g = x g_1$$ for some polynomial $$g_1$$.

Then $$a_n x^{n-1} = g_1 h$$, and repeating this argument $$n - 1$$ times shows $$g = b x^d$$ and $$h = c x^e$$ for some $$b, c, d + e = n$$. We now argue as before.

We can also prove the theorem more directly. Suppose $$f = g h$$ for polynomials $$g, h$$ with integer coefficients. Let

$g(x) = b_d x^d + ... + b_0$

and

$h(x) = c_e x^e + ... + c_0$

for some $$d + e = n$$. The conditions imply $$p$$ divides exactly one of $$b_0$$ and $$c_0$$. Without loss of generality, say $$p$$ divides $$b_0$$ but not $$c_0$$.

Since $$p$$ divides

$a_1 = b_1 c_0 + b_0 c_1$

we deduce $$p$$ divides $$b_1$$. We now know $$p$$ divides $$b_0, b_1$$ but not $$c_0$$.

Since $$p$$ divides

$a_2 = b_2 c_0 + b_1 c_1 + b_0 c_2$

we deduce $$p$$ divides $$b_2$$. We now know $$p$$ divides $$b_0, b_1, b_2$$ but not $$c_0$$.

Continuing in this manner on $$a_3 ... a_d$$, we conclude by induction that $$p$$ divides each of $$b_0 ... b_d$$.

But this implies $$p$$ divides $$b_d c_e = a_n$$, a contradiction.∎

## Gauss' Lemma

We usually combine Eisenstein’s criterion with the next 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 💡