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 axiomsnamely, 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) da (read: d divides a or a in a multiple of d or the equation dx = a has an integer solution x) and db. {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 nonnegative. 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 "bricklaying 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 nonzero 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 5th and 8th grade in China. I learned the gcd algorithm in a 5th grade class in China. By the 8th 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_(n1) ..... a_1 a_0
+) a*a_n ..... __________________________________ a_n a_(n1) + 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) = (xa)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 8th 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 17th 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 13th century is food for thought.
Han Sah SUNY at Stony Brook, L.I. New York sah@math.sunysb.edu



