x2
Introduction
=

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.