Associated Topics || Dr. Math Home || Search Dr. Math

### 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/
```
Associated Topics:
College Algorithms
College Definitions
College Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search