Let 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 Polynomials

A 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 polynomials

Two polynomials P

_{1}, P

_{2}, then P

_{1}, P

_{2}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

^{n}in the expression of P is not zero.

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

For any two polynomials P

_{1}, P

_{2}, there exists a GCD

Proof:

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

Definition 5: monic polynomial

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

Theorem 2:

Any two polynomials P

_{1}, P

_{2}∈ F[X] which are not both 0 have a unique monic greatest common divisor D

_{1}and a polynomial D ∈ F[X] is a greatest common divisor of P

_{1}, P

_{2}if and only if D=cD

_{1}for some c ∈ F

^{x}(= F - {0}).

Proof:

(1) Let P

_{1}∈ F[X] be polynomials such that deg P

_{1}is greater than deg P

_{2}

(2) Using Theorem 1 above, we know that there exists R

_{n}such that R

_{n}is the GCD of P

_{1}, P

_{2}

(3) Dividing R

_{n}by its leading coefficient gives us a monic GCD of P

_{1},P

_{2}

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

_{1}, P

_{2}

(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

_{1}, P

_{2}

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

_{1}, P

_{2}

(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

_{1}, P

_{2}, then there exists polynomials U

_{1}, U

_{2}such that:

D = P

_{1}U

_{1}+ P

_{2}U

_{2}where U

_{1}, U

_{2}∈ F[X]

Proof #1:

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

R

_{n-2}= Q

_{n}R

_{n-1}+ R

_{n}which gives us:

R

_{n}= R

_{n-2}- Q

_{n}R

_{n-1}

and likewise:

R

_{n-1}= R

_{n-3}- Q

_{n-1}R

_{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-1}R

_{n-2}) =

= R

_{n-2}- Q

_{n}R

_{n-3}+ Q

_{n}Q

_{n-1}R

_{n-2}=

= -R

_{n-3}Q

_{n}+ R

_{n-2}(1 +Q

_{n}Q

_{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

_{1}into P

_{1}, P

_{2}

(5) Eventually we get to an expression of R

_{n}such that:

R

_{n}= P

_{1}U

_{1}+ P

_{2}U

_{2}

QED

Proof #2:

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

P

_{1}= Q

_{1}P

_{2}+ R

_{1}

(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

_{2}= Q

_{2}R

_{1}+ R

_{2}

which gives us:

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

R

_{n-1}= Q

_{n+1}R

_{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

_{1}, U

_{2}, U

_{3}, U

_{4}such that:

(10) It now follows that:

(11) This then gives us that:

U

_{1}*P

_{1}+ U

_{2}*P

_{2}= R

_{n}

and

U

_{3}*P

_{1}+ U

_{4}*P

_{2}= 0

QED

Corollary 3.1:

If P

_{1}, P

_{2}are relatively prime polynomials in F[X], then there exists polynomials U

_{1}, U

_{2}such that:

P

_{1}U

_{1}+ P

_{2}U

_{2}= 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

## No comments :

Post a Comment