Greatest Common Divisor of a Polynomial and its First Derivative

Lemma 1:

Let a be a root of a polynomial P.

Then:

a is a multiple root of P if and only if a is also a root of P' (the first derivative of P)

Proof:

(1) Since a is a root of P, there exists a polynomial Q such that (see Theorem, here):

P = (x - a)Q

(2) Using the Product Rule of Derivatives (see Lemma 4, here), we know that:

P' = Q + (x-a)Q'

(3) But then (x-a) only divides P' if and only if it also divides Q.

QED

Corollary 1.1:

If a polynomial has only simple roots

Then:

Its first derivative does not share any of those roots.

Proof

(1) Assume that a polynomial P has only simple roots.

(2) Assume that a root a divides both P and P'

(3) Then by Lemma 1 above, a is a multiple root of P.

(4) But by step #1 this is impossible so we reject our assumption in step #2.

QED

Lemma 2:

If a polynomial P has only simple roots

Then P,P' are relatively prime.

Proof:

(1) Assume that P,P' are not relatively prime.

(2) Then, they have a common irreducible factor of degree 1.

[Since by definition, two polynomials are relatively prime if their only common factor is of degree 0]

(3) Then there exists a polynomial of the form X-a that divides both P and P' (See Thereom, here)

(4) Then from Lemma 1 above, a is a multiple root of P

(5) But this is impossible, so we reject our assumption in step #1.

QED

References

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

Alternate Form of the Greatest Common Divisor Algorithm for Polynomials

The usual form of the Greatest Common Divisor for Polynomials uses a series of steps of the form (see the proof for the usual form, here):

(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

But for Sturm's Theorem, I need to use an alternate form.

(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

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

If 1 is the GCD for polynomials P₁, P₂, then P₁, P₂ are said to relatively prime polynomials.

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: Alternate Form of 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 the alternate form of 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

References

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

Ring of Polynomials

If you are not comfortable with the idea of rings, start here.

Definition 1: Polynomial in one indeterminate with coefficients in a ring A

P : N → A such that P = { n ∈ N : P_n ≠ 0 }

where N is the set of natural numbers (that is, 0, 1, 2, ... )

As a convention, this mapping is usually represented in the form:

a_nxⁿ + a_n-1x^n-1 + ... + a₁x + a₀

where n ∈ N.

Example 1:

5x² + 3x + 2 is a polynomial.

5,3,2 are all integers which is a ring (see here for details on integers)

{ 2 → 5, 1 → 3, 0 → 2 }

Definition 2: Polynomial Addition

(P + Q)_n = P_n + Q_n

Example 2:

(5x² + 3x + 2) + (3x² + x + 5) = (5 + 3)x² + (3+1)x + (2+5) = 8x² + 4x + 7

Definition 3: Polynomial Multiplication

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

Example 3:

(5x² + 3x + 2)(3x² + x + 5) = (5*3)x⁽²⁺²⁾ + (5*1 + 3*3)x⁽²⁺¹⁾ + (5*5 + 3*1 + 2*3)x⁽²⁺⁰⁾ + (3*5 + 2*1)x⁽¹⁺⁰⁾ + (2*5)x⁰

Definition 4: A[X]

The set of all polynomials with coefficients in A

Example 4:

5x² + 3x + 2 ∈ Z[X] where Z is the set of all integers.

Lemma 1:

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

Proof:

(1) I will show that A[X] has all the properties of a ring.

(2) Commutative Property for Addition:

P_n + Q_n = (P + Q)_n = (Q + P)_n = Q_n + P_n

(3) Associative Property for Addition

(P_n + Q_n) + R_n = (P + Q)_n + R_n = ([P + Q] + R)_n = (P + [Q + R])_n

= P_n + (Q + R)_n = P_n + (Q_n + R_n)

(4) Additive Identity

This is the 0 polynomial. P_n + 0 = (P + 0)_n = P_n

(5) Additive Inverse

P_n + -P_n = (P + -P)_n = 0

(6) Associative Property for Multiplication

∑(i+j+k=n) (P_i*Q_j)*R_k = [(P*Q)*R]_n = [P*(Q*R)]_n = ∑ (i+j+k=n)P_i*(Q_j*R_k)

(7) Distributive Property for Multiplication

∑(i+j=n) P_i(Q_j + R_j) = ∑(i+j=n)P_i(Q + R)_j = [P(Q+R)]_n
= (PQ + PR)_n = ∑(i+j=n)(P_iQ_j) + ∑(i+j=n)(P_iR_j)

We can use the same argument to prove:

∑(i+j=n) (Q_j + R_j)P_i = ∑(i+j=n)(Q_jP_i) + ∑(i+j=n)(R_jP_i)

(8) Commutative Property for Multiplication is true if A has the Commutative Property for Multiplication

Assume that A is commutative.

∑(i+j=n)P_iQ_j = (PQ)_n = (QP)_n = ∑(i+j=n)Q_jP_i

QED

References

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

Degree of a Polynomial

Definition 1: Degree of a polynomial

The highest nonzero exponent is the degree of the polynomial.

As a convention, the degree of a zero polynomial is said to be -∞.

Lemma 1: deg(A+B) ≤ max(degA,degB)

Proof:

(1) We start with with deg A = 0, deg B=0 where A ≠ -B [We can ignore deg = - ∞ since by the Additive Identity Property (see here), it is true]

(2) A+B ≠ 0, so deg(A+B) = 0

(3) Assume that this is true up to deg A, deg B ≤ n-1.

(4) Let:

A = a_nxⁿ + ... + a₀

B = b_nx^n-1 + ... + b₀

(5) We can assume that a_n ≠ -b_n [Since if this is the case, the n degrees cancels out and the proposition is true by the inductive hypothesis.]

(6) a_n + b_n = (a+b)_n [See here for Additive Rule for Polynomials]

(7) So the deg(A+B) = n

QED

Lemma 2: deg(AB) = deg(A) + deg(B)

Proof:

(1) Assume deg A = 0, deg B = 0

(2) Then deg(AB) = 0 = 0 + 0

(3) Assume that the proposition is true up to n-1

(4) Let:

A = a_nxⁿ + ... + a₀

B = b_nx^n-1 + ... + b₀

(5) The highest exponent will be a_n*b_n = (a*b)_n+n

(6) deg(a*b)_n+n = 2n = deg(a) + deg(b)

QED

References

• "Degree of a Polynomial", Wikipedia.org
  

Alternate Form of the Division Algorithm for Polynomials

Theorem: Alternative Form of the Division Algorithm for Polynomials

Let F be a field

Let f(x),g(x) be polynomials of F[x] where g(x) ≠ 0

Then:

There exists unique polynomials q(x), r(x) in F[x] such that f(x) = g(x)q(x) - r(x) and r(x)=0 or deg r(x) is less than deg g(x)

Proof:

(1) Let f(x),g(x) be two polynomials such that g(x) ≠ 0

(2) We can assume that deg f(x) ≥ deg g(x) since:

if deg f(x) = 0, then f(x) = g(x)(0) - 0.

if deg f(x) is less than deg g(x), then f(x) = g(x)(0) - [-f(x)]

(3) Let:

f(x) = a_nxⁿ + ... + a₀

g(x) = b_mx^m + ... + b₀

where a_n and b_m are nonzero.

[We can make this assumption since g(x) ≠ 0 and deg f(x) ≥ deg g(x).]

(4) I will use induction to establish the existence of q(x), r(x).

(5) q(x),r(x) exist if deg f(x) = 0 since:

(a) Assume deg f(x) = 0

(b) Then there exists C such that f(x)=C

(c) Since deg f(x) ≥ deg g(x), it follows that deg g(x)= 0 and there exists D such that g(x)=D

(d) Let q(x) = C/D

(e) Then it follows that f(x) = g(x)*q(x) - 0

(6) Assume that our assumption holds true up to deg f(x) = n-1

(7) Let:

f₁(x) = f(x) - a_nb_m^-1x^n-mg(x)

(8) So, deg f₁(x) is less than deg f(x)

(9) By the induction hypothesis, there exists q₁(x) and r₁(x) such that:

f₁(x) = q₁(x)g(x) - r₁(x)

where deg r₁ is less than deg g(x) or deg r₁(x) = 0

(10) So, then:

f₁(x) + a_nb_m^-1x^n-mg(x) = a_nb_m^-1x^n-mg(x) + q₁(x)g(x) - r₁(x)

= [a_nb_m^-1x^n-m + q₁(x)]g(x) - r₁(x)

where deg r₁ is less than deg g(x) or deg r₁(x) = 0

(11) This proves the first part of the theorem. To complete it, we need to prove uniqueness.

(12) Assume that:

f(x) = g(x)q(x) - r(x) = g(x)q'(x) - r'(x)

where deg r(x), deg r'(x) = 0 or is less then deg g(x)

(13) So that:

0 = g(x)q(x) - r(x) - g(x)q'(x) + r'(x)

(14) Then:

r(x) - r'(x) = g(x)[q(x) - q'(x)]

(15) Assume that q(x) - q'(x) is nonzero.

(16) Then, deg g(x)[q(x)-q'(x)] = deg g(x) + deg (q(x) - q'(x)) [See Lemma 2, here]

(17) And, deg(r(x) - r'(x)) ≤ max(deg r(x),deg r'(x)) [See Lemma 1, here]

(18) But this is impossible since deg(r(x)) is less than deg g(x)

(19) So, we have a contradiction and we reject our assumption in step #15.

(20) So, if q(x) - q'(x) is 0, then it follows that r(x) - r'(x) is also 0.

(21) Then q(x) = q'(x) and r(x) = r'(x)

QED

Reference

• Joseph A. Gallian, Contemporary Abstract Algebra.

Inequality lemmas

Lemma 1: abs(a/b) ≤ 1 if and only if abs(a) ≤ abs(b)

Proof:

Case I: a,b are both positive

(1) Assume abs(a/b) ≤ 1

(2) a/b ≤ 1

(3) a ≤ b

(4) abs(a) ≤ abs(b)

(5) Assume abs(a) ≤ abs(b)

(6) a ≤ b

(7) a/b ≤ 1

(8) abs(a/b) ≤ 1

Case II: a,b are both negative

(1) Assume abs(a/b) ≤ 1

(2) a/b ≤ 1

(3) -a ≤ -b [since -b is positive]

(4) abs(a) ≤ abs(b)

(5) Assume abs(a) ≤ abs(b)

(6) -a ≤ -b

(7) a/b ≤ 1 [since -b is positive]

(8) abs(a/b) ≤ 1

Case III: Only b is negative

(1) Assume abs(a/b) ≤ 1

(2) -(a/b) ≤ 1

(3) (a/b) ≤ -1

(4) a ≤ -b [since b is negative and -b is positive]

(5) abs(a) ≤ abs(b) [ since abs(b) = -b ]

(6) Assume abs(a) ≤ abs(b)

(7) a ≤ -b

(8) a/b ≥ -1 [since b is negative]

(9) -(a/b) ≤ 1

(10) abs(a/b) ≤ 1

Case IV: Only a is negative

(1) Assume abs(a/b) ≤ 1

(2) -(a/b) ≤ 1

(3) -a ≤ b [since b is positive]

(4) abs(a) ≤ abs(b) [since abs(a) = -a and abs(b) = b]

(5) Assume abs(a) ≤ abs(b)

(6) -a ≤ b

(7) -a/b ≤ 1

(8) abs(a/b) ≤ 1

QED

Corollary 1.1: abs(a) is greater than abs(b) if and only if abs(a/b) greater than 1

Proof:

(1) Assume that abs(a) is greater than abs(b)

(2) Assume that abs(a/b) is not greater than 1

(3) Then abs(a/b) ≤ 1

(4) Then abs(a) ≤ abs(b) [From Lemma 1 above]

(5) But this contradicts step #1 so we reject our assumption in step #2.

(6) Assume that abs(a/b) is greater than 1.

(7) Assume that abs(a) is not greater than abs(b)

(8) Then abs(a) ≤ abs(b)

(9) Then abs(a/b) ≤ 1 [From Lemma 1 above]

(10) But this contradicts step #6 so we reject our assumption in step #7.

QED

Lemma 2:

if a,b,q are integers such that abs(a/b - q) is less than 1

Then:

There exists an integer c such that abs(a/b - c) is less than (1/2)

Proof:

(1) Assume abs(a/b - q) is greater than (1/2) [Otherwise, set c = q and we are done]

(2) if (a/b - q) is less than -1/2, then [a/b - (q-1)] is less than 1/2 and [a/b - (q-1)] is greater than 0

(3) if (a/b - q) is greater than 1/2, then [a/b - (q+1)] is greater than -1/2 and [a/b - (q+1)] is less than 0

QED

Corollary 2.1:

Let a,b be integers

if abs(a) ≤ abs(b)

Then:

There exists an integer c such that abs(a/b - c) is less than (1/2)

Proof:

(1) Assume abs(a) ≤ abs(b)

(2) Then abs(a/b) ≤ 1. [See Lemma 1 above]

(3) If (a/b) = 0, then c = 0 and the conclusion follows.

(4) if (a/b) ≥ -1, then abs(a/b + 1) is less than 1.

(5) if (a/b) ≤ 1, then abs(a/b - 1) is greater than -1.

(6) So, the conclusion follows from Lemma 2 above.

QED