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_{1} = Q_{3}R_{2} + R_{3}(b)

R_{2} = Q_{4}R_{3} + R_{4}...

(c)

R_{n-2} = Q_{n}R_{n-1} + R_{n}(d)

R_{n-1} = Q_{n+1}R_{n} + R_{n+1}But for Sturm's Theorem, I need to use an alternate form.

(a)

R_{1} = Q_{3}R_{2} - R_{3}(b)

R_{2} = Q_{4}R_{3} - R_{4}...

(c)

R_{n-2} = Q_{n}R_{n-1} - R_{n}(d)

R_{n-1} = Q_{n+1}R_{n} - R_{n+1}

Definition 1: Divisor for PolynomialsLet

P_{1}, P_{2} ∈ F[X].

We say that

P_{2} divides P_{1} if there exists

Q ∈ F[X] such that P

_{1} = P

_{2}Q

Definition 2: GCD for PolynomialsA

greatest common divisor (GCD) of

P_{1}, P_{2} is a polynomial

D ∈ F[X] which has the following properties:

(a)

D divides

P_{1} and

P_{2}(b) If

S is a polynomial which divides

P_{1} and

P_{2}, then

S divides

D.

Definition 3: Relatively prime polynomialsIf

1 is the

GCD for polynomials

P_{1}, P_{2}, then

P_{1}, P_{2} are said to

relatively prime polynomials.

Definition 4: degree: degThe

deg of a polynomial

P is the greatest integer

n for which the coefficient

X^{n} in the expression of

P is not zero.

Theorem 1: Alternate Form of Euclid's Algorithm for Greatest Common Divisor for PolynomialsFor any two polynomials

P_{1}, P_{2}, there exists a

GCDProof:

(1) Let

P_{1}, P_{2} be any two polynomials such that

deg P_{1} ≥ deg P_{2}(2) If

P_{2} = 0, then

P_{1} is the

GCD of

P_{1}, P_{2} [See Definition 2 above]

(3) Otherwise, we divide

P_{1} by

P_{2} using the

the alternate form of Euclidean Division Algorithm for Polynomials. [See Theorem,

here]

(4) Then there exists two polynomials

Q_{1}, R_{1} such that:

P_{1} = Q_{1}P_{2} - R_{1}and

deg R_{1} is less than

deg P_{2}.

(5) If

R_{1} = 0, then

P_{2} is the

GCD of

P_{1}, P_{2}(6) Next, we divide

P_{2} by

R_{1} to get:

P_{2} = Q_{2}R_{1} - R_{2}and

deg R_{2} is less than

deg R_{1}(7) If

R_{2} ≠ 0, then we can set up the following equations:

(a)

R_{1} = Q_{3}R_{2} - R_{3}(b)

R_{2} = Q_{4}R_{3} - R_{4}...

(c)

R_{n-2} = Q_{n}R_{n-1} - R_{n}(d)

R_{n-1} = Q_{n+1}R_{n} - R_{n+1}(8) Since

deg P_{2} is greater than

deg R_{1} which is greater than

deg R_{2} 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_{1}, P_{2} 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_{2} and

R_{3} before it, it is clear from 7a, that

R_{n} divides

R_{1}It is clear from step #6 that

R_{n} divides

P_{2} and clear from step #4 that

R_{n} divides

P_{1}(11) Assume that

P_{1} and

P_{2} are both divisible by a polynomial

S.

(12) Then by step #4,

S must divide

R_{1}.

(13) By step #6,

S must divide

R_{2}(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_{1},P_{2} [See Definition 2 above]

QED

References