One tool we are going to need in our toolbox is a way to find the greatest common divisor (GCD) of two numbers.
You probably learned the basic idea in elementary school; since and , the greatest common divisor of 20 and 15 is 5. But once again, we need to worry about how hard such a problem is as the problem size grows; in this case, it turns out not to be particularly difficult, but it is worth learning how to do it.
Euclid himself, perhaps the most famous of the ancient Greek mathematicians for his work on geometry, developed (or at least wrote down) an algorithm for GCD, based on repeated subtraction. The algorithm is best explained by example, so let’s look for the GCD of 126 and 72. Begin by subtracting the smaller number from the larger one, and repeating until we reach zero:
and the last non-zero number is our GCD. and , so . You may well have recognized that , so we could have terminated the algorithm a couple of steps earlier.
The algorithm has a beautiful visualization. To find , create a rectangle that is . Begin filling it with the largest squares that will fit (one or more squares the size of the smaller of and ). In the remaining rectangle, perform the same operation. Repeat until the original rectangle is filled. The edge length of the smallest size of square is the GCD. The Exercise in the next Step lets you play with the algorithm and see for yourself how it works.
This algorithm is efficient in the terms that we described last week; it will run in time that is polynomial in the number of digits in the numbers.
© Keio University