Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
Drexel University or The Math Forum.
|
|
|
|
Long (Posting on) Division Algorithm
Posted:
Feb 23, 1995 9:52 AM
|
|
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
|
|
|
|
