# Euclid's Algorithm

It's good to have a general definition of "divides" but more often, we're interested in "divisibility", i.e. when does one number divide or "go into" another.

Let's think for a minute about what the equation from the end of the last section,

"If *a* = *qb* + *r* then gcd(*a*, *b*) = gcd(*b*, *r*)."

really gets us. Remember that *r* is the remainder from dividing *b* into *a*. This means it's got to be less than *b* so right hand part of the statement, the part after the equals sign, gives us a way to relate the gcd of two numbers, *a* and *b*, to the gcd of two smaller numbers, *b* and *r*.

Here's how this helps us with practical problems. Say I asked you to find gcd(1024, 612). Using the Division Algorithm we can write

1024 = 612 · 1 + 412

and according to our formula this means gcd(1024, 612) = gcd(612, 412). That's nice, I suppose, but 612 and 412 are also big numbers. If I apply the Division Algorithm again to 612 and 412, I'll reduce the numbers further and if I do it again they'll be reduced even further, etc. The whole process goes like this:

1024 | = | 612 | * | 1 | + | 412 | so gcd(1024, 612) = gcd(612, 412) |

612 | = | 412 | * | 1 | + | 200 | so gcd(1024, 612) = gcd(412, 200) |

412 | = | 200 | * | 2 | + | 12 | so gcd(1024, 612) = gcd(200, 12) |

200 | = | 12 | * | 16 | + | 8 | so gcd(1024, 612) = gcd(12, 8) |

12 | = | 8 | * | 1 | + | 4 | so gcd(1024, 612) = gcd(8, 4) |

8 | = | 4 | * | 2 | + | 0 | so gcd(1024, 612) = gcd(4, 0) |

The process stops when the remainder becomes 0. Finding gcd(4, 0) is easy - any number goes into 0 and the biggest number that goes into 4 is 4 so gcd(4, 0) = 4 but because gcd(1024, 612) = gcd(4, 0) we must also have gcd(1024, 612) = 4.

This process, reducing the gcd of two big numbers to the gcd of two smaller numbers, is called Euclid's Algorithm and first appears in book four of his *Elements* which was published around 300 B.C.

What makes this process especially useful is that it can be programmed into a computer more easily that the brute force, "list all the factors" approach can. For practical purposes, as we'll see a few lessons down the road, it can also be used to simplify the process of finding the least common denominator of two fractions.