The Euclidian Algorithm finds: The Greatesd Common Divisor of two numbers.

Last Up date: 2018 December 10 on nuMacMini work/gd/lafarr/math
2003 November 26 version

Integers: a divided by b can be written as an equation: a=bq+r (Where q is the quotient and r is the remainder.)
r can be 0 through b-1 i.e. r < b

Said another way r=a-bq

If it turns out a and b have a common divisor k, one could say:
a=kn and b=km substituting these for a and b in the above.
r=kn-kmq or r=k(n-mq) which tells us that r must also be divisible by k.

If that worked once we can do it again: divide b by r (both have the common divisor k) and get a new remainder (smaller than r) that also has the divisor k. Simply repeat this until one of the successively smaller remainders becomes zero. The last divisor is k generally called "The Greatest Common Divisor".

Example: Finding largest divisor of 76,084 and 63,020

 We start doing the divides at the right side of our "page". ``` 8 2 1 4 1 4 1 92)736)1564)2300)10764)13064)63020)76084 736 1472 1564 9200 10764 52256 63020 0 92 736 1564 2300 10764 13064 ```Thus, we have found 92 divides both 76,084 and 63,020 92 is divisable by: 2,4, and 23 so each of these divides either of the original two numbers.

For this the quotients are ignored!

The process of repeatedly dividing the remainder into the divisor is the Euclidian Algorithm. It was known prior to 300 BC, but is not taught today in most of our schools. There is also a Subtraction Version which some may feel is simpler.

But, there is a use for those quotients!

The mathematically inclined may know: 1,4,1,4,1,2,8 is the Continued Fraction representation of 76084/63020)=(827/685). It is used for generating "best" approximations.

 Look at the quotients: 1,4,1,4,2,8 in the order generated. Spread out a little ` 1 4 1 4 1 2 8` ```0 1 1 5 6 29 35 99 827 1 0 1 4 5 24 29 82 685``` ```S L S L S L S L = ```The 2nd and 3rd lines above are fractions with the numerator on the second line and the denominator on the third. In the line above the "S" and the "L" indicates if the fraction is Smaller or Larger than the value being approximated. Yes, they always alternate. Consequently, the error of any fraction is less than the difference between it and the next one. Note: (76084/63020)=(827/685)=1.2072992... and (6/5)=1.20 (29/24)=1.2083... (35/29)=1.20689...
See how to create the 2nd and 3rd lines, and the Continued Fraction representation of the Square Root of 2.

Pi to 50 decimal places 3,14159 26535 89793 23846 26433 83279 50288 41971 69399 37510

Converted to Continued Fractions Sat 2003-11-22 using IA.COM
 ```3 7 15 1 292 1 1 1 2 1 3 1 14 2 1 1 2 2 2 2 1 84 2 1 1 15 3 13 1 4 2 6 6 99 1 2 2 6 3 5 1 1 6 (The following are correct for the 50 digit truncated approximation of Pi. But, a more accurate value for Pi gives 8 instead of 9 for the next value, and different following values. The following values are not correct for Pi, but they are correct for this 50 place value which is less than Pi.) 9 3 2 1 1 1 17 2 33 1 6 2 5 1 1 1 26 1 4 10 1 1 4 2 6 2 3 2 1 65 2 1 13 1 8 1 1 18 10 2 3 1 3 1 7 1 1 3 ``` Yes, I did convert a 1000 digit approximation, but decided for here this is enough, and I wanted to make a point about approximate values. It is interesting to change the last digit 0 to a 1 and convert that larger than Pi value.

Multiple precision division was necessary.

E-mail me or Click the phone block to call or get link to my BIO page.

 Go to: My Home Page Go to: This page TOP