Euclidean Algorithm

Date: 10/13/97 at 11:47:58
From: Kevin Duong
Subject: Euclid's theorem

I have this project to do that involves Euclid's theorem (actually 
it's about the Greatest Common Denominator). Can you tell me what it 
is in layman's terms, or try to simplify it, please?

Thanks,
Kevin

Date: 10/16/97 at 12:20:45
From: Doctor Ezra
Subject: Re: Euclid's theorem

Dear Kevin,

Euclid had a number of theorems, but I suspect that the one you're 
interested in is also known as the Euclidean Algorithm. This is an 
algorithm, or procedure, for finding the Greatest Common Divisor (or
GCD) of two numbers, and it's based on something with which you are 
probably familiar.

But first, what's the GCD of two numbers? It's just the largest number 
that divides both numbers exactly, leaving no remainder. For example, 
the divisors of 6 are 1, 2, 3 and 6, and the divisors of 15 are 1, 3, 
5 and 15, so the GCD of 6 and 15 is the largest number to appear on 
both lists: 3. In the same way, you can check to see that the GCD of 
36 and 210 is 6, and that the GCD of 15 and 8 is 1.

Euclid knew that if you divide one number by another, you get a 
quotient and a remainder, and that the remainder is less than the 
divisor. For instance, if you divide 7 into 39, it goes 5 times 
(that's the quotient) with a remainder of 4: 39 = 5*7 + 4. 
Also, divide 17 into 829: it goes 48 times, with 13 left over: 
829 = 816 + 13 = 48*17 + 13.

So, said Euclid, to find the GCD of two numbers, divide one of them 
into the other, and I guarantee that the GCD will also exactly divide 
the remainder. For example,

  210 = 5*36 + 30

the GCD of 210 and 36 is 6, and 6 does divide 30 exactly (30 = 5*6). 

Now divide the old remainder into the old divisor, and the GCD of the 
old divisor and the old remainder will exactly divide the new 
remainder. Keep doing this, said Euclid, until you get a remainder of 
0. The last nonzero remainder you get will be the GCD of the two 
numbers you started with. 

Let's do this with 210 and 36:

  210 = 5*36 + 30  Divisor 36, remainder 30
   36 = 1*30 + 6   Divisor 30, remainder 6
   30 = 5*6  + 0   Divisor  6, remainder 0.

So, 6 is the last nonzero remainder, and that's the GCD of 210 and 36.

Try this out with 21 and 36, with 21 and 34, and with 288 and 178. 

Good luck!

-Doctor Ezra,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/