Saturday, December 08, 2007

Irreducible Polynomials

Definition 1: Irreducible Polynomials

A polynomial P ∈ F[X] is irreducible in F[X] if deg P is greater than 0 and P is not divisible by any polynomial Q ∈ F[X] such that 0 is less than deg Q is less than deg P.

NOTE: See Definition 1, here, for definition of polynomials and Definition 4, here, for definition of deg of a polynomial.

Lemma 1:

If a polynomial D divides an irreducible polynomial P,

Then, either D is a constant or deg D = deg P.


(1) Let P be an irreducible polynomial

(2) Let D be a polynomial that divides P.

(3) Assume that D is not a constant and that deg D is less than deg P.

(4) Then D cannot divide P [by Definition 1 above]

(5) So we have a contradiction and we must reject our assumption at step #3.


Corollary 1.1: Every polynomial of degree 1 is irreducible

(1) Assume that there exists a polynomial D of degree 1 that is not irreducible.

(2) Then there exists a polynomial P that divides D where deg P is less than deg D and deg P is greater than 0.

(3) But this is impossible since deg D = 1 (either deg P = 0 or deg P ≥ 1).

(4) So we reject our assumption at step #1.


Theorem 2: Euclid's Lemma for Polynomials

For polynomials S,T,U if S divides TU and S is relatively prime to T, then S divides U.


(1) Since GCD(S,T)=1, there exists polynomials V,W such that [See Corollary 3.1, here]:

SV + TW = 1

(2) Multiplying both sides by U gives us:

S(UV) + (TU)W = U

(3) This proves that S divides U since S divides TU.


Corollary 2.1: Generalized Euclid's Lemma for Polynomials

If a polynomial S divides a product of r factors and is relatively prime to the first r-1 factors, then it divides the last one.


(1) Let T = the first r-1 factors.

(2) Let U = the last factor

(3) Then S divides TU and GCD(S,T)=1 so using Theorem 2 above, we can conclude that S divides U.


Corollary 2.2: If a polynomial is divisible by pairwise relatively prime polynomials, then it is divisible by their product


(1) Let P1, ..., Pr be relatively prime polynomials which divide a polynomial P.

(2) For r=1, P1 = P so the corollary is true.

(3) Assume that it is true up to r-1.

(4) So, then we have:

P = P1*..*Pr-1*Q

(5) By Corollary 2.1 above, since Pr divides P, it follows that Pr must divide Q.

(6) So, then it follows that P1...*...*Pr must divide P.


Theorem 3: Every non constant polynomial P ∈ F[X] is a finite product:

P = cP1P2...Pn

where c ∈ Fx and P1, P2, ..., Pn are monic irreducible polynomials where this factorization is unique. Order of these polynomials is not unique and there may include repeats of the same polynomial more than once.


(1) If P is irreducible, then P = c*P1 where c is the leading coefficient of P and P1 = c-1P is irreducible and monic. [See Definition 1 above and Theorem 2, here]

(2) If P is reducible, then it can be written as a product of two polynomials of degree less than deg P.

(3) If the two polynomials less than P are irreducible, then we are done. If not, then we can continue to break each reducible polynomial into a product of reducible polynomials and then using step #1, we break this product into the desired result.

(4) The next step is to prove that this product independent of order is unique.

(5) Assume that:

P = cP1*...*Pn = dQ1*...*Qm

where c,d ∈ Fx and P1, ..., Pn, Q1, ..., Qm are irreducible polynomials.

(6) c = d since both equal the leading coefficient of P.

(7) So, we have:

P1*...*Pn = Q1*...*Qm

(8) Using Corollary 2.1 above, we know that P1 cannot be relatively prime to all Qi

(9) So, let's assume that there exists a Qi such that GCD(P1,Qi) ≠ 1. Let's label it Q1

(10) Let D be the unique monic GCD of P1,Q1. [See Theorem 2, here]

(11) Since P1 is irreducible, then P1 = cD for some c.

(12) Since P1 is monic, then c = 1 and P1 = D.

(13) Since Q1 is monic and irreducible, we can use the same argument as in steps #11 and steps #12 to establish that Q1 = D.

(14) Therefore, it follows that Q1 = P1

(15) We can make the same argument for all n elements of Pi so that we have P2 = Q2, P3 = Q3, ..., Pn = Qn

(16) Since there must be a matched element for each Pi, it follows that n ≤ m.

(17) But we can also make the same line of argument for Qj so that we also know that m ≤ n

(18) Therefore n = m.



No comments :