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.

Proof:

(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.

QED

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.

QED

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.

Proof:

(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.

QED

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.

Proof:

(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.

QED

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

Proof:

(1) Let P₁, ..., P_r be relatively prime polynomials which divide a polynomial P.

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

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

(4) So, then we have:

P = P₁*..*P_r-1*Q

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

(6) So, then it follows that P₁...*...*P_r must divide P.

QED

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

P = cP₁P₂...P_n

where c ∈ F^x and P₁, P₂, ..., P_n 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.

Proof:

(1) If P is irreducible, then P = c*P₁ where c is the leading coefficient of P and P₁ = 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 = cP₁*...*P_n = dQ₁*...*Q_m

where c,d ∈ F^x and P₁, ..., P_n, Q₁, ..., Q_m are irreducible polynomials.

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

(7) So, we have:

P₁*...*P_n = Q₁*...*Q_m

(8) Using Corollary 2.1 above, we know that P₁ cannot be relatively prime to all Q_i

(9) So, let's assume that there exists a Q_i such that GCD(P₁,Q_i) ≠ 1. Let's label it Q₁

(10) Let D be the unique monic GCD of P₁,Q₁. [See Theorem 2, here]

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

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

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

(14) Therefore, it follows that Q₁ = P₁

(15) We can make the same argument for all n elements of P_i so that we have P₂ = Q₂, P₃ = Q₃, ..., P_n = Q_n

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

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

(18) Therefore n = m.

QED

References

• Jean-Pierre Tignol, Galois' Theory of Algebraic Equations, World Scientific, 2001
  

Greatest Common Divisor for Polynomials

Definition 1: Divisor for Polynomials

Let P₁, P₂ ∈ F[X].

We say that P₂ divides P₁ if there exists Q ∈ F[X] such that P₁ = P₂Q

Definition 2: GCD for Polynomials

A greatest common divisor (GCD) of P₁, P₂ is a polynomial D ∈ F[X] which has the following properties:

(a) D divides P₁ and P₂
(b) If S is a polynomial which divides P₁ and P₂, then S divides D.

Definition 3: Relatively prime polynomials

Two polynomials P₁, P₂, then P₁, P₂ are said to relatively prime polynomials if the only factors they have in common are of degree 0.

Definition 4: degree: deg

The deg of a polynomial P is the greatest integer n for which the coefficient Xⁿ in the expression of P is not zero.

Theorem 1: Euclid's Algorithm for Greatest Common Divisor for Polynomials

For any two polynomials P₁, P₂, there exists a GCD

Proof:

(1) Let P₁, P₂ be any two polynomials such that deg P₁ ≥ deg P₂

(2) If P₂ = 0, then P₁ is the GCD of P₁, P₂ [See Definition 2 above]

(3) Otherwise, we divide P₁ by P₂ using the Euclidean Division Algorithm for Polynomials. [See Theorem, here]

(4) Then there exists two polynomials Q₁, R₁ such that:

P₁ = Q₁P₂ + R₁

and deg R₁ is less than deg P₂.

(5) If R₁ = 0, then P₂ is the GCD of P₁, P₂

(6) Next, we divide P₂ by R₁ to get:

P₂ = Q₂R₁ + R₂

and deg R₂ is less than deg R₁

(7) If R₂ ≠ 0, then we can set up the following equations:

(a) R₁ = Q₃R₂ + R₃

(b) R₂ = Q₄R₃ + R₄

...

(c) R_n-2 = Q_nR_n-1 + R_n

(d) R_n-1 = Q_n+1R_n + R_n+1

(8) Since deg P₂ is greater than deg R₁ which is greater than deg R₂ which is greater than ... deg R_n which is greater deg R_n+1, this sequence cannot extend indefinitely.

(9) Therefore, R_n+1 = 0 for some n.

(10) R_n divides P₁, P₂ since:

Because R_n+1=0, R_n divides R_n-1

Because R_n divides R_n-1, from equation 7c, R_n divides R_n+1

We can now proceed up each of these implied equations in the same way until we get to 7b.

Since we have shown that R_n divides R₂ and R₃ before it, it is clear from 7a, that R_n divides R₁

It is clear from step #6 that R_n divides P₂ and clear from step #4 that R_n divides P₁

(11) Assume that P₁ and P₂ are both divisible by a polynomial S.

(12) Then by step #4, S must divide R₁.

(13) By step #6, S must divide R₂

(14) We can now use the same argument to go through the equations in step #7 to conclude that S must likewise divide R_n.

(15) This proves that R_n is the GCD for P₁,P₂ [See Definition 2 above]

QED

Definition 5: monic polynomial

A polynomial is monic if and only if its leading coefficient is 1.

Theorem 2:

Any two polynomials P₁, P₂ ∈ F[X] which are not both 0 have a unique monic greatest common divisor D₁ and a polynomial D ∈ F[X] is a greatest common divisor of P₁, P₂ if and only if D=cD₁ for some c ∈ F^x (= F - {0}).

Proof:

(1) Let P₁ ∈ F[X] be polynomials such that deg P₁ is greater than deg P₂

(2) Using Theorem 1 above, we know that there exists R_n such that R_n is the GCD of P₁, P₂

(3) Dividing R_n by its leading coefficient gives us a monic GCD of P₁,P₂

(4) Assume that D, D' are GCD's of P₁, P₂

(5) Then D divides D' and D' divides D. [See Definition 2 above]

(6) Then there exists polynomials Q,Q' ∈ F[X] such that:

D' = DQ
D = D'Q'

(7) So that:

Q = D'/D
Q' = D/D'

QQ' = (D'/D)(D/D') = 1

(8) But since Q'Q=1, they must both be constants which are inverses of each other.

(9) So, if D and D' are monic, then Q=Q'=1 and D=D' [Otherwise if Q ≠ 1, then D'=DQ would imply that D' is not be monic]

(10) Suppose D is any GCD of P₁, P₂

(11) Let D' be the unique monic GCD of P₁, P₂

(12) Let a = the leading coefficient of D.

(13) It is clear that (1/a)D = D' since the monic GCD is unique [see Step #9 above]

QED

Theorem 3:

If D is the GCD of P₁, P₂, then there exists polynomials U₁, U₂ such that:

D = P₁U₁ + P₂U₂ where U₁, U₂ ∈ F[X]

Proof #1:

(1) Using step #7c from Theorem 1 above, we have:

R_n-2 = Q_nR_n-1 + R_n

which gives us:

R_n = R_n-2 - Q_nR_n-1

and likewise:

R_n-1 = R_n-3 - Q_n-1R_n-2

(2) We can then use the same type of equation to resolve R_n-1 to get:

R_n = R_n-2 - Q_n(R_n-3 - Q_n-1R_n-2) =

= R_n-2 - Q_nR_n-3 + Q_nQ_n-1R_n-2 =

= -R_n-3Q_n + R_n-2(1 +Q_nQ_n-1)

(3) We've now put R_n in terms of R_n-3 and R_n-2

(4) In this way, we can eliminate each R_i in terms of R_i-1 and R_i-2 up until we resolve R₁ into P₁, P₂

(5) Eventually we get to an expression of R_n such that:

R_n = P₁U₁ + P₂U₂

QED

Proof #2:

(1) From step #4 of Theorem 1 above, we have:

P₁ = Q₁P₂ + R₁

(2) Using Matrix Theory (see here for review of 2 x 2 matrices), this gives us:



(3) From step #6 of Theorem 1 above we have:

P₂ = Q₂R₁ + R₂

which gives us:



(4) We can continue this approach until step #7d:

R_n-1 = Q_n+1R_n + R_n+1

which gives us:



(5) Combining the matrix equations gives us:



(6) Now, since we know that:





(7) We see that each:



is invertible (see here for review of invertibility of matrices).

(8) We can then rearrange the equation in step #5 to be:



(9) Now, we can define U₁, U₂, U₃, U₄ such that:



(10) It now follows that:



(11) This then gives us that:

U₁*P₁ + U₂*P₂ = R_n

and

U₃*P₁ + U₄*P₂ = 0

QED

Corollary 3.1:

If P₁, P₂ are relatively prime polynomials in F[X], then there exists polynomials U₁, U₂ such that:

P₁U₁ + P₂U₂ = 1

Proof:

Since for relatively prime polynomials GCD = 1, this result follows directly from Theorem 3 above.

QED

References

• Jean-Pierre Tignol, Galois' Theory of Algebraic Equations, World Scientific, 2001

Polynomials defined

A polynomial expression is a mathematical construct that if often used and rarely defined. The most common form is a polynomial in one variable which can be represented as:
a₀xⁿ + a₁x^n-1 + ... + a_(n-1)x + a_n

In today's blog, I will present a more formal definition and then show the very fundamental result that a polynomial is a ring. If you are not familiar with rings, then please start here.

The content in today's blog is taken from Jean Tignol's excellent Galois' Theory of Algebraic Equations.

Definition 1: Polynomial in one indeterminant with coefficients in ring A

P: N → A such that { n ∈ N : P_n ≠ 0 } is finite. The set of all polynomials in one indeterminant with coefficients in ring A can be denoted as A[X].

Example 1:

Let us consider the polynomial:

a₀ + a₁X + ... + a_nXⁿ

In this case, each a_i is a coefficient in ring A.

We can see that for each i, that i ∈ N and that there exists an integer n ∈ N such that:

if i ≤ n, then i ∈ N maps to a_i.

if i is greater than n, then i ∈ N maps to 0.

Definition 2: Addition of Polynomials

(P + Q)_n = P_n + Q_n

In other words, each of the maps corresponding to the same natural number are added together to form a new map.

Definition 3: Multiplication of Polynomials

(PQ)_n = ∑ (i+j=n) P_i*Q_j

In other words, each of the maps corresponding to the multiplication of all maps where the index of one plus the index of the other = n.

Lemma 1: If A is a ring, then A[X] is a ring which is commutative if and only if A is commutative

Proof:

(1) A[X] is a ring since:

(a) A[X] has a commutative operation of addition

P + Q = P_i + Q_i for all i.

Q + P = Q_i + P_i for all i.

Since A is a ring, P_i + Q_i = Q_i + P_i

(b) A[X] has an associative rule for addition

(P + Q) + R = (P_i + Q_i) + R_i for all i

P + (Q + R) = P_i + (Q_i + R_i) for all i

(P_i + Q_i) + R_i = P_i + (Q_i + R_i) since A is a ring.

(c) A[X] has an additive identity

Let Q be a polynomial such that all Q_i map to 0.

Then for any polynomial P, it is clear that P + Q = P_i + 0 = P_i for all i.

(d) A[X] has an additive inverse

For any polynomial P:

Let Q be a polynomial derived from P such that for all i: Q_i = -P_i

Then

P + Q = P_i + -P_i = 0 for all i.

(e) A[X] has an associative rule for multiplication

PQ = ∑ (i+j=n) P_i*Q_j for all n

(PQ)R = ∑ (i+j+k=n) (P_i*Q_j)R_k for all n =

= ∑ (i+j+k=n) P_i*(Q_jR_k) for all n

QR = (j+k=n) Q_j*R_k for all n

P(QR) = ∑ (i+j+k=n) P_i*(Q_jR_k) for all n

(f) A[X] has a distributive rule

Q + R = Q_j + Rj for all j

P(Q+R) = ∑ (i+j=n) P_i*(Q_j + R_j) =

= ∑ (i+j=n) P_iQ_j + P_iR_j

PQ = ∑ (i+j=n) P_i*Q_j for all n

PR = ∑ (i+j=n) P_i*R_j for all n.

PQ + PR = ∑ (i+j=n) P_iQ_j + ∑(i + j=n) P_iR_j for all n =

= ∑(i+j=n) P_iQ_j + P_iR_j

(Q+R)P = ∑ (i+j=n) (Q_j + R_j)*P_i =

= ∑ (i+j=n) P_iQ_j + P_iR_j

(2) If A is a commutative ring, then A[X] is a commutative ring.

(a) Assume that A is a commutative ring

(b) PQ = ∑ (i+j=n) P_i*Q_j for all n =

= ∑ (i+j=n) Q_j*P_i for all n = QP

(3) If A[X] is a commutative ring, then A is a commutative ring

(a) Assume that A[X] is a commutative ring

(b) QP = PQ = ∑ (i+j=n) P_i*Q_j for all n

(c) QP = ∑ (i+j=n) Q_j*P_i for all n

(d) So, therefore for all n, ∑ (i+j=n) P_i*Q_j = ∑ (i+j=n) Q_j*P_i

QED

References

• Jean-Pierre Tignol, Galois' Theory of Algebraic Equations, World Scientific, 2001

Breakdown of rational fractions as sums of partial fractions

Lemma 1: Rational fraction as sum of relatively prime polynomials

If P,Q,S₁,S₂ are polynomials such that:

Q = S₁S₂

S₁,S₂ are relatively prime polynomials

Then, there exists polynomials P₀, P₁, P₂ such that:

P/Q = P₀ + P₁/S₁ + P₂/S₂

deg P_i is less than deg S_i for both i=1 and i=2

Proof:

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

1 = S₁T₁ + S₂T₂

(2) Multiply each side by P/Q to get:

P/Q = (PS₁T₁)/Q + (PS₂T₂)/Q

(3) Since Q=S₁S₂, we now have:

P/Q = (PS₁T₁)/(S₁S₂) + (PS₂T₂)/(S₁S₂) = (PT₁)/S₂ + (PT₂)/S₁

(4) By the Euclidean Division Algorithm for Polynomials (see Theorem, here), there exists U₁, U₂, R₁, R₂ such that:

PT₁ = S₂U₂ + R₂

where deg R₂ is less than deg S₂

PT₂ = S₁U₁ + R₁

where deg R₁ is less than deg S₁

(5) Replacing PT₁ and PT₂ in step #3 gives us:

P/Q = (S₂U₂ + R₂)/S₂ + (S₁U₁ + R₁)/S₁ =

= (S₂U₂)/S₂ + R₂/S₂ + (S₁U₁)/S₁ + R₁/S₁ =

= (U₂ + U₁) + R₁/S₁ + R₂/S₂

QED

Lemma 2:

For polynomials Q,P:

If Q is irreducible and deg P is less than deg Q^m, then:

P/Q^m = P₁/Q + P₂/Q² + ... + P_m/Q^m

where deg P_i is less than deg Q for i = 1, ..., m

Proof:

(1) Using Euclidean Division for Polynomials (see Theorem, here), there exists P₁,R₁ such that:

P = P₁Q^m-1 + R₁ where deg R₁ is less than deg Q^m-1

(2) deg P₁ is less than deg Q since:

(a) Assume deg P₁ ≥ deg Q

(b) Then P₁Q^m-1 is greater than deg Q^m

(c) But this is impossible since deg P is less than deg Q^m and since P₁Q^m-1 is less than P.

(d) So we reject our assumption at step #2a.

(3) We can now repeat this same step with P₂ as a quotient for Q^m-2 and so on.

(4) Eventually, we get to:

P = P₁Q^m-1 + P₂Q^m-2 + ... + P_m-1Q + P_m

(5) If we now divide both sides by Q^m, we get:

P/Q^m = P₁/Q + P₂/Q² + ... + P^m-1/Q^m-1 + P^m/Q^m

QED

References

• Jean-Pierre Tignol, Galois' Theory of Algebraic Equations, World Scientific, 2001