Definition 1: Divisor for PolynomialsLet
P1, P2 ∈ F[X].
We say that
P2 divides P1 if there exists
Q ∈ F[X] such that P
1 = P
2Q
Definition 2: GCD for PolynomialsA
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 polynomialsTwo polynomials
P1, P2, then
P1, P2 are said to
relatively prime polynomials if the only factors they have in common are of degree 0.
Definition 4: degree: degThe
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: Euclid's Algorithm for Greatest Common Divisor for PolynomialsFor any two polynomials
P1, P2, there exists a
GCDProof:
(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
Euclidean Division Algorithm for Polynomials. [See Theorem,
here]
(4) Then there exists two polynomials
Q1, R1 such that:
P1 = Q1P2 + R1and
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 + R2and
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-1Because
Rn divides
Rn-1, from equation 7c,
Rn divides
Rn+1We 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
R1It 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
Definition 5: monic polynomialA polynomial is
monic if and only if its leading coefficient is
1.
Theorem 2: Any two polynomials
P1, P2 ∈ F[X] which are not both
0 have a unique
monic greatest common divisor
D1 and a polynomial
D ∈ F[X] is a greatest common divisor of
P1, P2 if and only if
D=cD1 for some
c ∈ Fx (= F - {0}).Proof:
(1) Let
P1 ∈ F[X] be polynomials such that
deg P1 is greater than
deg P2(2) Using Theorem 1 above, we know that there exists
Rn such that
Rn is the
GCD of P1, P2(3) Dividing
Rn by its leading coefficient gives us a monic
GCD of P1,P2(4) Assume that
D, D' are
GCD's of
P1, P2(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' = DQD = D'Q'(7) So that:
Q = D'/DQ' = 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
P1, P2(11) Let
D' be the unique monic
GCD of
P1, P2(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
P1, P2, then there exists polynomials
U1, U2 such that:
D = P1U1 + P2U2 where
U1, U2 ∈ F[X]Proof #1:
(1) Using step #7c from Theorem 1 above, we have:
Rn-2 = QnRn-1 + Rn
which gives us:
Rn = Rn-2 - QnRn-1and likewise:
Rn-1 = Rn-3 - Qn-1Rn-2(2) We can then use the same type of equation to resolve
Rn-1 to get:
Rn = Rn-2 - Qn(Rn-3 - Qn-1Rn-2) == Rn-2 - QnRn-3 + QnQn-1Rn-2 == -Rn-3Qn + Rn-2(1 +QnQn-1)(3) We've now put
Rn in terms of
Rn-3 and
Rn-2(4) In this way, we can eliminate each
Ri in terms of
Ri-1 and
Ri-2 up until we resolve
R1 into
P1, P2(5) Eventually we get to an expression of
Rn such that:
Rn = P1U1 + P2U2QED
Proof #2:
(1) From step #4 of Theorem 1 above, we have:
P1 = Q1P2 + R1(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:
P2 = Q2R1 + R2
which gives us:

(4) We can continue this approach until step #7d:
Rn-1 = Qn+1Rn + Rn+1which 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
U1, U2, U3, U4 such that:

(10) It now follows that:

(11) This then gives us that:
U1*P1 + U2*P2 = Rnand
U3*P1 + U4*P2 = 0QED
Corollary 3.1: If
P1, P2 are relatively prime polynomials in
F[X], then there exists polynomials
U1, U2 such that:
P1U1 + P2U2 = 1Proof:
Since for relatively prime polynomials
GCD = 1, this result follows directly from Theorem 3 above.
QED
References