Associated Topics || Dr. Math Home || Search Dr. Math

### 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/
```
Associated Topics:
High School Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search