Euclidean and Division Algorithms

Date: 11/26/97 at 03:48:36
From: Terry
Subject: Polynomial

Can you show and explain the proofs of the Euclidean Algorithm and the 
Division Algorithm?

Date: 11/26/97 at 11:57:47
From: Doctor Rob
Subject: Re: Polynomial

Since your subject is "Polynomial," I assume you are talking about 
these algorithms as applied to polynomials with coefficients in a 
field, such as the complex numbers, real numbers, or rational numbers, 
as opposed to being applied to integers.

First the Division Algorithm.  It is based on the theorem that given 
two polynomials F(x) and D(x) with D(x) nonzero, there exist 
polynomials Q(x) and R(x) such that F(x) = Q(x)*D(x) + R(x), and the 
degree of R is less than the degree of D.  Q is called the quotient, 
and R the remainder, when F is divided by D.

The proof of this theorem goes like this:

If F(x) = 0, then set Q(x) = 0 and R(x) = 0, and we are done.

If F(x) is not zero, let the leading term of F(x) be A*x^f, and the 
leading term of D(x) be B*x^d, with both A and B nonzero, f >= 0, and 
d >= 0.

If f < d, we can use Q(x) = 0, R(x) = F(x), and we are done.

If f >= d, then construct the polynomials T0(x) = (A/B)*x^(f-d), and

   F1(x) = F(x) - D(x)*T0(x).

This has been designed so that the leading term of F(x) will be 
canceled by the leading term of D(x)*T0(x), since both are equal to 
A*x^f.

If F1(x) = 0, then set Q(x) = T0(x) and R(x) = 0, and we are done.

If F1(x) is not zero, let the leading term of F1(x) be A1*x^f1, where 
A1 is nonzero and f > f1 >= 0.

If f1 < d, we can use Q(x) = T0(x) and R(x) = F1(x), and we are done.

If f1 >= d, then construct the polynomials T1(x) = (A1/B)*x^(f1-d), 
and

   F2(x) = F1(x) - D(x)*T1(x).

This has been designed so that the leading term of F1(x) will be 
canceled by the leading term of D(x)*T1(x), since both are equal to 
A1*x^f1.

If F2(x) = 0, then set Q(x) = T0(x) + T1(x) and R(x) = 0, and we are 
done.

If F2(x) is not zero, let the leading term of F2(x) be A2*x^f2, where 
A2 is nonzero and f > f1 > f2 >= 0.

We continue this process until either one of the Fn's is zero or has 
degree less than d.  That this must happen is guaranteed by the 
decreasing sequence of nonnegative integer degrees 

  f > f1 > f2 > ... >= 0, 

which can have at most f + 1 terms.  The process must end after 
n <= f + 1 steps. Then 

  Q(x) = T0(x) + T1(x) + ... + Tn(x), and R(x) = Fn(x).

An alternate proof can be constructed using mathematical induction.

Example:  Find the quotient and remainder of F(x) = x^4 - 3*x^2 + 2*x
divided by D(x) = x^3 + x^2 - 2.

Here f = 4, d = 3, A = B = 1.  T0(x) = (1/1)*x^(4-3) = x.

   F1(x) = F(x) - D(x)*T0(x),
         = x^4 - 3*x^2 + 2*x - (x^3 + x^2 - 2)*x,
         = x^4 - 3*x^2 + 2*x - x^4 - x^3 + 2*x,
         = -x^3 - 3*x^2 + 4*x.

Now f1 = 3 and A1 = -1, so T1(x) = (-1/1)*x^(3-3) = -1.

   F2(x) = F1(x) - D(x)*T1(x),
         = -x^3 - 3*x^2 + 4*x - (x^3 + x^2 - 2)*(-1),
         = -x^3 - 3*x^2 + 4*x + x^3 + x^2 - 2,
         = -2*x^2 + 4*x - 2.

Since this has degree less than 3, we are done, and Q(x) = x - 1, and
R(x) = -2*x^2 + 4*x - 2.


Now for the Euclidean Algorithm. It uses the Division Algorithm. The
appropriate theorem is the following.

Given two polynomials F0(x) and F1(x) with F1(x) nonzero, construct a
sequence of polynomials Q2, Q3, ... and F2, F3, ... in the following 
way. Use the division algorithm at each step.

   F0(x) = Q2(x)*F1(x) + F2(x),  0 <= deg(F2) < deg(F1)
   F1(x) = Q3(x)*F2(x) + F3(x),  0 <= deg(F3) < deg(F2)
   ...
   Fk-2(x) = Qk(x)*Fk-1(x) + Fk(x),  0 <= deg(Fk) < deg(Fk-1)
   Fk-1(x) = Qk+1(x)*Fk(x).

Then Fk(x) is a nonzero constant multiple of the greatest common 
divisor of F0(x) and F1(x).

Proof:  Let D(x) be the greatest common divisor of F0(x) and F1(x).  
Use the principal of mathematical induction to show that Fk(x) divides 
Fi(x) for all i with 0 <= i <= k. Use it again to show that any common 
divisor of F0(x) and F1(x) divides Fi(x) for all i with 0 <= i <= k.  
Use in those induction steps the equations given above, and the fact 
that if D divides A and D divides B, then it divides A + B and A - B 
and A*C and B*C for any C. Together, the divisibility of any common 
divisor into Fk(x), and the fact that Fk(x) is a common divisor of 
F0(x) and F1(x), imply that Fk(x) divides D(x), and D(x) divides 
Fk(x).  Thus Fk(x) = c*D(x) for some nonzero constant c.

Example:  Find the GCD of F0(x) = x^4 - 3*x^2 + 2*x and
F1(x) = x^3 + x^2 - 2.

   x^4 - 3*x^2 + 2*x = (x - 1)*(x^3 + x^2 - 2) + (-2*x^2 + 4*x - 2),
   x^3 + x^2 - 2 = ([-1/2]*x-3/2)*(-2*x^2 + 4*x - 2) + (5*x - 5)
   -2*x^2 + 4*x - 2 = ([-2/5]*x+2/5)*(5*x - 5).

Thus 5*x - 5 is a nonzero constant multiple of the G.C.D., which is 
always taken to be monic (leading coefficient 1), so the G.C.D. is 
x - 1.

-Doctor Rob,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/