(a) R1 = Q3R2 + R3
(b) R2 = Q4R3 + R4
...
(c) Rn-2 = QnRn-1 + Rn
(d) Rn-1 = Qn+1Rn + Rn+1
But for Sturm's Theorem, I need to use an alternate form.
(a) R1 = Q3R2 - R3
(b) R2 = Q4R3 - R4
...
(c) Rn-2 = QnRn-1 - Rn
(d) Rn-1 = Qn+1Rn - Rn+1
Definition 1: Divisor for Polynomials
Let P1, P2 ∈ F[X].
We say that P2 divides P1 if there exists Q ∈ F[X] such that P1 = P2Q
Definition 2: GCD for Polynomials
A greatest common divisor (GCD) of P1, P2 is a polynomial D ∈ F[X] which has the following properties:
(a) D divides P1 and P2
(b) If S is a polynomial which divides P1 and P2, then S divides D.
Definition 3: Relatively prime polynomials
If 1 is the GCD for polynomials P1, P2, then P1, P2 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 Xn 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 P1, P2, there exists a GCD
Proof:
(1) Let P1, P2 be any two polynomials such that deg P1 ≥ deg P2
(2) If P2 = 0, then P1 is the GCD of P1, P2 [See Definition 2 above]
(3) Otherwise, we divide P1 by P2 using the the alternate form of Euclidean Division Algorithm for Polynomials. [See Theorem, here]
(4) Then there exists two polynomials Q1, R1 such that:
P1 = Q1P2 - R1
and deg R1 is less than deg P2.
(5) If R1 = 0, then P2 is the GCD of P1, P2
(6) Next, we divide P2 by R1 to get:
P2 = Q2R1 - R2
and deg R2 is less than deg R1
(7) If R2 ≠ 0, then we can set up the following equations:
(a) R1 = Q3R2 - R3
(b) R2 = Q4R3 - R4
...
(c) Rn-2 = QnRn-1 - Rn
(d) Rn-1 = Qn+1Rn - Rn+1
(8) Since deg P2 is greater than deg R1 which is greater than deg R2 which is greater than ... deg Rn which is greater deg Rn+1, this sequence cannot extend indefinitely.
(9) Therefore, Rn+1 = 0 for some n.
(10) Rn divides P1, P2 since:
Because Rn+1=0, Rn divides Rn-1
Because Rn divides Rn-1, from equation 7c, Rn divides Rn+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 Rn divides R2 and R3 before it, it is clear from 7a, that Rn divides R1
It is clear from step #6 that Rn divides P2 and clear from step #4 that Rn divides P1
(11) Assume that P1 and P2 are both divisible by a polynomial S.
(12) Then by step #4, S must divide R1.
(13) By step #6, S must divide R2
(14) We can now use the same argument to go through the equations in step #7 to conclude that S must likewise divide Rn.
(15) This proves that Rn is the GCD for P1,P2 [See Definition 2 above]
QED
References
- Jean-Pierre Tignol, Galois' Theory of Algebraic Equations
, World Scientific, 2001
No comments :
Post a Comment