3.10

# Euclid's Algorithm

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 $20 = 5\times 4$ and $15 = 5\times 3$, 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:

$126 - 72 = 54$
$72 - 54 = 18$
$54 - 18 = 36$
$36 - 18 = 18$
$18 - 18 = 0$

and the last non-zero number is our GCD. $126 = 7\times 18$ and $72 = 4\times 18$, so $\mathrm{gcd}(126,72) = 18$. You may well have recognized that $54 = 3\times 18$, so we could have terminated the algorithm a couple of steps earlier.

The algorithm has a beautiful visualization. To find $\mathrm{gcd}(x,y)$, create a rectangle that is $x\times y$. Begin filling it with the largest squares that will fit (one or more squares the size of the smaller of $x$ and $y$). 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 in the first week, when we talked about computational complexity; it will run in time that is polynomial in the number of digits in the numbers.