[an error occurred while processing this directive]

The Greatest Common Divisor (GCD),
or Euclidean, Algorythm


        This algorythm incorporates the traditional approach along with an extension that makes possible finding the greatest common (integer) divisor from among an infinite number of integers rather than from just two integers. For example, if you wanted to find the gcd of 20 and 8, the traditional approach would have no problem with this situation. It would discover 4 as the gcd of 20 and 8. But what if the gcd were sought for: 10, 8, and 20? Traditionally, one would need to find the gcd among all combinations of 10, 8, and 20, namely, the gcd of: 10 and 8, 8 and 20, and 10 and 20, and then pick the lowest solution found from among the three pairings. [At least this is what my college professor taught us, circa 1994.] If the gcd were sought for a huge beavy of numbers, say a thousand, this would be a nightmarish computation! Not so, saith the blind man......

The following method is predicated on the presumption that there is a solution involving an integer greater than one: 


First,
Sort the three numbers from smallest to largest and from left
to right. It is arbitrary which direction you choose. Just be
consistent:
 8				 10				 20
Next,
Subtract from each number lying to the right of the left-most
column the largest multiple of that number for the purpose of
producing the smallest (positive) integer remainder possible
for that column:
-0				 -8 (8 * 1)			-16 (8 * 2)
--				 --				---
 8				  2				  4


Resort them again in the same manner as above and repeat the
subtraction process until all columns to the right of the left-
most column zero out:
 2				  4				  8
-0				 -4 (2 * 2)			 -8 (2 * 4)
--				 --				 --
 2				  0				  0


 2 is the GCD of 8, 10, and 20

        In this example, it appears to be somewhat advantageous over using the traditional method. Even though all three columns of numbers maintain themselves right up to the very end result, this doesn't always occur. Often times, various columns will get wiped out progressively, as you compute along, making further computation a lot easier. The third column on the right would have wiped itself out to zero had I used the method below which is strictly kosher. Ergo, the above method is not the way to do this......

        Now consider setting up the initial three values of this "cubic" example of the Euclidean Algorythm with the three values of the seventh iteration of the golden, cubic, number series: 157, 126, and 70: 


First,
Sort the three numbers from smallest to largest or from
largest to smallest (your choice):
 70				 126				  157
Next,
Subtract from each number the largest multiple of its immediate
lessor for the purpose of producing the smallest (positive)
integer remainder possible. Of course, this means that the
smallest number of the three will not have anything subtracted
from it:
- 0				- 70 (70 * 1)		- 126 (126 * 1)
---				----				-----
 70				  56				   31


Resort (if necessary) and repeat the subtraction process until
all numbers, but one, zero out:
 31				  56				  70
- 0				- 31 (31 * 1)		- 56 (56 * 1)
---				----				----
 31				  25				  14


 14				  25				  31
- 0				- 14 (14 * 1)		- 25 (25 * 1)
---				----				----
 14				  11				   6


  6				  11				  14
- 0				-  6 (6 * 1)			- 11 (11 * 1)
---				----				----
  6				   5				   3


  3				   5				   6
- 0				 - 3 (3 * 1)			 - 5 (5 * 1)
---				 ---				 ---
  3				   2				   1


  1				   2				   3
- 0				 - 1 (1 * 1) [2]		 - 2 (2 * 1)
---				 ---				 ---
  1				   1				   1


  1				   1				   1
- 0				 - 1 (1 * 1)			 - 1 (1 * 1)
---				 ---				 ---
  1				   0				   0


  1 is the GCD of 70, 126, and 157

        It could be said that these three numbers: 70, 126, and 157 have unity in common as far as the Euclidean Algorythm is concerned. They are primally, unique toward one another in a golden fashion: primal, because the number 1 is the only multiple ever used (within this algorytm) to relate them toward one another and golden, due to the nature of this algorythm constructing them in chain-like, aggregate fashion. [2] could have been used rather than 1 as a multiple above (although the end result would have been the same: 1 would still result as the GCD of all three initial values). So, there seems to be a formalism involved here to insure that all three numbers reduce to several zeros and a single 1 at the same time.
 
 
Next Lesson: How does the Greatest Common Divisor Algorythm arise out of algebra? Continued Fractions.

[an error occurred while processing this directive] [an error occurred while processing this directive] [an error occurred while processing this directive]

http://vinyasi.info/vinyasi/older-1st-version/book/gcd.shtml
Monday, 16 August 2004 15:29:58 MST [an error occurred while processing this directive]