LaFarr's Euclidean Algorithm

Is everyone familiar with the Euclidian Algorithm?

Last Up date: 2009 June 22
Recent changes: Tried to simulate Paper/Pencile division in the example.

a divided by b can be written as the 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

The Euclidean Algorithm is useful to find the Greatest Common Divisor of any two numbers.
For this the quotients are ignored!

This 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.

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.

Yes, these types of calculations require division by big values. Multiple precision division is necessary.

Now lets look at techniques for Long Division.

You can: E-mail me or Click on the phone numbers for my BIO:

Go to: My Home Page