Date: Feb 23, 1995 9:52 AM Author: Chih-Han sah Subject: Long (Posting on) Division Algorithm

One of the nicest uses of the Division Algorithm is to

find the greatest common divisor of two integers a and b. The

same idea works for polynomials (where the coefficients satisfy

the field axioms--namely, having the same formal arithmetic

properties as the rational numbers with respect to +, -, x, and /).

One may begin with a slightly modified definition of gcd

in the following form:

Definition of gcd. Let a, b be integers. d is called

*a* gcd of a and b when it has the following two properties:

(a) d|a (read: d divides a or a in a multiple of d or

the equation dx = a has an integer solution x)

and d|b. {Thus, d is a common divisor of a and b.}

(b) If d'|a and d'|b, then d'|d. {Thus, d is a multiple

of every other common divisor of a and b and is

the 'greatest' in the sense that a divisor is

'smaller'. This interpretation is the usual one

when a, b, d are restricted to the positive integers.

However, it is not to be taken literally when dealing

with polynomials.}

Example: one gcd of 4, 6 is -2 and the other one is +2.

Exercise: If a, b are nonzero, then the possible gcds of

a and b differ from each other by a divisor of 1

(in the case of integers, this means that they

differ from each other by a factor of 1 or -1).

Exercise: gcd(a,b) "=" gcd(b,a) ("=" may be read as

"being associates of each other" or as having

the same absolute value in the case of integers.

Thus, gcd(a,b) = gcd(|a|,|b|) and we may concentrate

on the case where a, b are both non-negative.

In the case of polynomials, we may concentrate

on polynomials with highest coefficient equal to

1 when the polynomial is not zero).

Exercise: If a or b is zero, then gcd(a,b) "=" is the

other number. Namely, gcd(0,b) "=" b and

gcd(a,0) "=" b.

We now remind the students the division algorithm in the

following form.

Division Algorithm: Let a, b be two integers with |b| not zero.

Then there exist uniquely determined integers q and r with

the following two properties:

(i) a = bq + r

(ii) 0 <= r < |b|

One may give a geometric "brick-laying proof" by laying off

segments (bricks) of length |d| either to the right or to the

left of zero (the starting point) on a line (the numbers

line) and cite axioms of Euclidean geometry. A purely algebraic

proof can be carried using induction.

At this point, one may introduce

GCD algorithm (or "down a ladder algorithm").

Let a and b be non-zero integers. Then a gcd of a and b

can be obtained by the following procedure in a finite

number (at most |b|) steps.

Divide b into a and write: a = qb + r, 0 <= r < |b|.

Then gcd(a,b) "=" gcd(r,b). (This is to be read in

the form: gcd is not changed if a is replaced by

the remainder upon division of a by b. In particular,

if r = 0, then by Exercise, gcd(a,b) "=" gcd(0,b) "=" b.)

If 0 < r < |b|, then divide r into b and write:

g = q'r + r', 0 <= r' < r.

Thus, gcd(a,b) "=" gcd(r,b) "=" gcd(r,r').

By alternating left and right, in a finite number (at most |b|

steps), we will reach a zero for the remainder and the

gcd is the preceding nonzero remainder (unless both a and b

are zero).

To remember the conclusion, one may picture the entire process as one

of coming down a ladder. First the left foot comes down, then the

right foot comes down, etc. When one foot reaches ground (remainder

zero), then the other foot gives the gcd.

The proof is quite easy. Namely, using the exerices above,

we may assume a, b > 0. Let a = qb + r, 0 <= r < b.

To see that gcd(a,b) "=" gcd(r,b), we note that any

common divisor of a and b must divide r = a -qb as well as

r (use the associate and distributive properties of multiplication).

Thus a gcd of (a,b) (if it exists) must be a divisor of gcd(r,b).

Conversely, any common divisor of r and b must diver a = qb + r

as well as b by the same reason.

Example: Let a = 3,405 and b = 1,205.

3405 = 2*1205 + 995

1205 = 1*995 + 210

995 = 4*210 + 155

210 = 1*155 + 65

155 = 2*65 + 25

65 = 2*25 + 15

25 = 1*15 + 10

15 = 1*10 + 5

10 = 2*5 + 0.

therefore, gcd(3405,1205) = 5 because this is the remainder just

before we get the remainder 0.

Of course, in the present case, a student may also factor each of the numbers

into a product of prime factors. The entire point is to avoid this process.

Namely, when a, b have many digits, e.g. 10 digits, the factorization

process becomes extremely tedious even on a computer. This is well

known to number theorists for hundreds of years. There is not much

more than using the "sieve method", namely, first divide by 2, then by 3,

by 5, by 7, etc. If your PC has a program that would factor numbers, you

might ask it to factor 2^127 - 1, a number with about 40 digits in the

decimal notation and see what happens (this number is a prime).

In particular, it is a good idea to do this before one introduce the

idea of prime numbers and the unique factorization theorem. The difficulty

in factorizing numbers into product of primes have been cleverly applied

to design "secure codes". It is very fashionable to establish new

records in factorizing large numbers by using collaborations of many,

many high speed computers and lots and lots spare computation time.

The reason for this seemingly resource wasting effort is to test out

the current capability of computers to accomplish the task of breaking

secure codes so that the users have some idea how "secure" is the

"secure code".

I am told that the division algorithm in the above form

is not taught in the U.S. schools. In fact, the gcd algorithm is

often not taught even in college level abstract algebra class.

When I showed presented the above material to teachers in an

algebra for teachers class, the universal agreement was that the

procedure is simple enough that they believe it can be taught in

a school algebra class. This and other "algorithms" were taught

between the 5-th and 8-th grade in China. I learned the gcd

algorithm in a 5-th grade class in China. By the 8-th grade,

we studied the method for solving systems of 3 linear equations

in 3 unknowns.

It should be made clear that the algorithm does not help

trying to speed up the factorization of a given number N. Although

the statement was that it takes at most |b| steps to find the gcd,

it is actually possible (using negative numbers) to speed things

up. Namely, no more than the number of binary digits needed to

express |b|.

To be precise, given nonzero numbers a and b. We can find q and r

so that a = qb + r with 0 <= |r| <= |b|/2. For example,

when we reached 995 and 210, we may write:

995 = 5*210 - 55

210 = 4*55 -10

55 = 5*10 + 5

10 = 2*5 + 0

(At every stage, we can work with the absolute value of

the remainder from the previous step and there is no restriction

on q and r being positive. We lose the uniqueness of q and

r in this procedure. For example, 55 = 6*10 - 5. However,

the advantage of this process is that the remainder shrinks

by a factor of 2 each time. If the numbers are written to

the base 2, then the number of steps needed is no more than

the number of binary digits needed to express the smaller

of the two numbers in absolute value. For example, something

like 2^127 - 1 has 127 binary digits. Finding gcd with

any other number b takes at most 127 steps. We do not have

to cheat and use the information that 2^127 - 1 is a prime

number so that its gcd with b is either 1 or 2^127 - 1.

*************

Along this vein, it is a good exercise to ask the students

to draw an analogy between numbers and polynomials. Namely,

3405 = 3*10^3 + 4*10^2 + 0*10^1 + 2*10^0, this looks like

a polynomial "in 10" with coefficients from the basic set

of digits: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}.

In doing synthetic division of polynomials, we often omit

the powers of X and keep track of the coefficients in the

proper places. This is nothing more than the analogue of

writing out numbers in decimal notation rather than as

"polynomial in 10".

The basic difference is that we have to worry about "carrying"

in arithmetics for the integers and do not have to worry about

it in arithmetics for polynomials. In this sense, polynomials

are less complicated than numbers. Of course, this is not

quite right because we still have to do arithmetics for the

coefficients which are numbers. The right way of saying this

is "once we understand arithmetics for numbers", extension

to polynomials is not more complicated. We just have to

do them for the coefficients and understand the procedure

for combining the coefficients in addition and in multiplication

of polynomials.

One may illustrate the idea of trying to find roots by

synthetic division. Namely, to test if a is a root of

a polynomial, we arrange the coefficient in the following

form:

a| a_n a_(n-1) ..... a_1 a_0

+) a*a_n .....

__________________________________

a_n a_(n-1) + a*a_n , etc

Example: Test to see if x = 4 is a root of X^3 - 3X^2 + 4.

4| 1 -3 0 4

+) 4 4 16

_________________

1 1 4 20

The quotient polynomial is X^2 + X^1 + 4 and remainder is 20.

Namely, 1, 1, 4 are the coefficients of the quotient polynomial

and the last number, 20, is the remainder.

In general x = a is a root if and only if the remainder term is 0.

This is just the special case of the division algorithm:

f(x) = (x-a)q(x) + r, where r is a constant.

This procedure can be repeated with different values of a to

get at an approximate solution of the polynomial equation

f(x) = 0.

This method is essentially the one used in the ancient Chinese

math texts by 1,000 AD

"Extracting roots through iterated multiplication."

In the west, it comes under the name of "Horner's method" which dates

back to Horner (1819) and was in fact found earlier by Ruffini (1804).

The special cases of degree 2 and 3 polynomials were already present

in Chinese math. texts dating back to about 100 BC.

The method for solving systems of 3 linear equations in 3

unknowns was essentially the one in use in Chinese math texts dating

back to 100 BC. It predates the Gaussian Elimination method by close

to 2000 years.

These methods were included in elementary school math. texts

during the Chinese school reform that began near the end of the last

Dynasty (around 1900). As far as I know, they were included in the

school math. texts (prior to 1949) no later than the 8-th grade.

All these may sound incredible, but the Chinese were very tradition

oriented and things are passed down from generation to generation and

with succeeding generation of mathematicians trying to improve on

what was passed down. Many of the "less practical" but advanced

works were lost for long periods until they were rediscovered. Apparently,

the elementary methods were retained. In these texts, problems were

given in "story form" and there were no "rigorous proofs" in the

form of Euclidean geometry proofs. One sees the "proof" only by analyzing

the solutions that accompany the problems. Thus, there were difficulties

in terms of "clarity". The influence of western mathematical thoughts

began in earnest in the beginning of 17-th century with the translation

of part of Euclid's elements and this was not completed until 250 years

later. The general opinion of Sinologists was that the stagnation of

science and mathematics in China had much to do with the governing

structure and the social conditions in China.

I apologize for the length of this posting. It is not intended

to advertise Chinese accomplishments. In fact, what had happened in

China since the 13-th century is food for thought.

Han Sah

SUNY at Stony Brook, L.I. New York

sah@math.sunysb.edu