Thursday, January 31, 2008

Eisenstein: Criteria for Irreducibility of Polynomials

In today's blog, I will go over a classical result from Ferdinand Eisenstein. The content in today's proof is taken directly from Jean-Pierre Tignol's Galois' Theory of Algebraic Equations.

I will later use this result in Carl Friedrich Gauss's proof that all roots of unity are expressible as radicals.

For those who are not familiar, a monic polynomial is a polynomial whose leading coefficient is 1.

Theorem 1: Eisenstein's Criteria for Irreducibility of Polynomials

Let P be a monic polynomial with integral coefficients such that:

P = Xt + ct-1Xt-1 + ... + c1X + c0 ∈ Z[X]

If there is a prime number p which divides ci for i = 0, ..., t-1 but p2 does not divide c0

then:

P is irreducible over Q

Proof

(1) Assume that P is not irreducible over Q.

(2) Then there exist two non-constant polynomials f,g ∈ Q[X] such that:

P = fg

(3) Assume that f has degree n with n ≥ 1 and g has degree m with m ≥ 1 so that:

f = Xn + an-1Xn-1 + ... + a1X + a0 ∈ Z[X]

g = Xm + bm-1Xm-1 + ... + b1X + b0 ∈ Z[X]

(4) Since P is monic, we can assume that f,g are monic [if f,g are not monic, then (f/an is monic and an*g is monic since P = (f/an)*(g*an)]

(5) From step #2, it is also clear that c0 = a0*b0

(6) Using Euclid's Lemma (see Lemma 2, here), it is clear that for the prime p, p divides a0 or b0.

(7) It is also clear that since p2 does not divide c0 that p cannot divide both a0 and b0.

(8) We can assume that p divides a0 but not b0 (if it did not, we could switch f,g since they are interchangeable with respect to p and make the same assumption)

(9) Let i be the largest index of a such that p divides ai. It is clear that 0 ≤ i ≤ n-1. So, we can conclude that for any i, p divides a0, a1, ..., ai.

(10) Let k = i+1, it is clear that 1 ≤ k ≤ n and p does not divide ak.

(11) So:

ci+1 = ai+1b0 + aib1 + ai-1b2 + ... + a0bi+1.

where bj = 0 if j is greater than m.

(12) Now i+1 ≤ n which is less than t since n+1 ≤ m+n = t [since m ≥ 1 and n ≥ 1]

(13) So it follows that i+1 ≤ t-1 and p divides ci+1. [From the given in the theorem that p divides c0, ..., ct-1]

(14) So, from step #13, it follows that since p divides ci+1 and p divides a0, a1, ..., ai [step #9] that p must also divide ai+1b0.

(15) But this is impossible since p doesn't divide b0 (step #8) and p doesn't divide ai+1 [step #10]

(16) So we have a contradiction and we must reject our assumption in step #1.

QED

Corollary 1.1: For every prime p, the cyclotomic polynomial

Φp(x) = xp-1 + xp-2 + ... + x + 1

is irreducible over the field of rational numbers

Proof:

(1) From the definition of the cyclotomic polynomial (see Definition 1, here):

Φp(x) = (xp - 1)/(x - 1)

(2) Setting x = y + 1, we get:

Φp(y+1) = ([y + 1]p - 1)/([y + 1] - 1) =

= ([y + 1]p - 1)/y

(3) Using the Binomial Theorem (see Theorem, here):

(4) So, combining this with step #2 gives us:

(5) Now, it is clear that for (y+1)p all the resulting coefficients are integral (since integers are closed on additional and multiplication, see Lemma 1 and Lemma 2, here).

(6) Further, we know that for p!/[(m!)(p-m)!] where 1 ≤ m ≤ p-2, p is not divisible by (m!) or by (p-1)! [Since p is a prime and only divisible by p and m! and (p-m)! does not include p]

(7) So, we can conclude that for m=1, ..., p-2, we have p divides p!/[(m!)(p-m)!]

(8) Now, we can use Eisenstein's Criterion above to conclude that the cyclotomic polynomial is irreducible in the field Q since:

the cyclotomic polynomial is monic, p divides all coefficients except for the leading coefficient, and p2 does not divide the last coefficient (p2 does not divide p.)

QED

References
• Jean-Pierre Tignol, , World Scientific, 2001