Eisenstein's criterion

In mathematics, Eisenstein's criterion gives sufficient conditions for a polynomial to be irreducible over Q (or equivalently, over Z).
Suppose we have the following polynomial with integer coefficients.
 <math>f(x)=a_nx^n+a_{n1}x^{n1}+\ldots+a_1x+a_0<math>
Suppose there exists a prime number p such that
 p divides each a_{i} for i ≠ n
 p does not divide a_{n}
 p^{2} does not divide a_{0}
Then f(x) is irreducible.
Examples
Consider g(x) = 3x^{4} + 15x^{2} + 10.
We test the following primes p.
 p = 2
 2 does not divide 15, so try
 p = 3
 3 does not divide 10, so try
 p = 5
 5 does divide 15, the coefficient of x, and 10, the constant term. Also, 5 does not divide 3, the leading coefficient. Finally, 25 = 5^{2} does not divide 10.
So, we conclude that g(x) is irreducible.
In some cases the prime to choose can be unclear, but can be revealed by a change of variable y = x + a, which is often referred to as a shift.
For example consider h(x) = x^{2} + x + 2. This looks difficult as no prime will divide 1, the coefficient of x. But if we shift h(x) to h(x + 3) = x^{2} + 7x + 14 we see instantly that the prime 7 divides the coefficient of x and the constant term and that 49 cannot divide 14. So by shifting the polynomial we have made it satisfy Eisenstein's criterion.
Another celebrated case is that of the cyclotomic polynomial for a prime p. This is
(x^{p} − 1)/(x − 1) = x^{p − 1} + x^{p − 2} + ... + x + 1.
Here, the polynomial satisfies Eisenstein's criterion, in a new variable y after setting x = y + 1. The constant coefficient is then p; the other coefficients are divisible by p by properties of binomial coefficients C(p,k) that are p! divided by something not involving p.
Basic proof
Consider f(x) as a polynomial modulo p; that is, reduce the coefficients to the field Z/pZ. There it becomes c.x^{n} for a nonzero constant c. Because such polynomials factorise uniquely, any factorisation of f mod p must be into monomials. Now if f were not irreducible as an integer polynomial, we could write it as g.h, and f mod p as the product of g mod p and h mod p. These latter must be monomials, as has just been said, meaning that we have g mod p is d.x^{k} and h mod p is e.x^{nk} where c = d.e.
Now we see that the conditions given on g mod p and h mod p mean that p^{2} will divide a_{0}, a contradiction to the assumption. In fact a_{0} will be g(0).h(0) and p divides both factors, from what was said above.
Advanced explanation
Applying the theory of the Newton polygon for the padic number field, for an Eisenstein polynomial, we are supposed to take the lower convex envelope of the points
 (0,1), (1, v_{1}), (2, v_{2}), ..., (n − 1, v_{n1}), (n,0),
where v_{i} is the padic valuation of a_{i} (i.e. the highest power of p dividing it). Now the data we are given on the v_{i} for 0 < i < n, namely that they are at least one, is just what we need to conclude that the lower convex envelope is exactly the single line segment from (0,1) to (n,0), the slope being −1/n.
From the general theory we know that p then ramifies completely in the extension of the padic numbers generated by a root of f. For that reason f is irreducible over the padic field; and a fortiori over the rational number field.
This argument is much more complicated than the direct argument by reduction mod p. It does however allow one to see, in terms of algebraic number theory, how frequently Eisenstein's criterion might apply, after some change of variable; and so, limit severely the possible choice of p.
In fact only primes p ramifying in the extension of Q generated by a root of f have any chance of working. These can be found in terms of the discriminant of f. For example in the case x^{2} + x + 2 given above, the discriminant is −7 so that 7 is the only prime that has a chance of making it satisfy the criterion. Mod 7, it becomes
 (x − 3)^{2}
— a repeated root is inevitable, since the discriminant is 0 mod 7. Therefore the variable shift is actually something predictable.
Again, for the cyclotomic polynomial, it becomes
 (x − 1)^{p − 1} mod p;
the discriminant can be shown to be (up to sign) p^{p − 2}, by linear algebra methods.