Algorithms for GCD – Big Stuff Going On

In this post, we’ll talk about how to find the greatest common divisor (gcd) of two numbers. We’ll start with the definition and get an algorithm for computing the gcd. Then we’ll talk about some properties of the gcd and how these lead to faster algorithms: the euclidean algorithm the binary gcd algorithm.

The definition of greatest common divisor (gcd)

Given an integer $a$ , the divisors of $a$ are the positive integers $d$ such that $a$ divided by $d$ has remainder 0. In other words, $d$ is a divisor of $a$ if the value of $a/d$ is an integer.

Yet another way to say this is that $d$ is a divisor of $a$ if we can find some integer $n=a/d$ such that

$a = d\cdot n$

If we have another integer $b$ , we can ask whether $d$ is also a divisor of $b$ . Maybe $d$ is a divisor of both. That is, $a/d$ and $b/d$ could both be integers (even if they are different integers).

Given two integers $a$ and $b$ , a common divisor of $a$ and $b$ is any integer $d$ which is a divisor of both $a$ and $b$ . At least one common divisor will exist, because both $a$ and $b$ have the number 1 as a divisor.

The greatest common divisor of $a$ and $b$ is the biggest integer we can find among the list of common divisors of $a$ and $b$ .

Example

Let $a=12$ and $b=20$ . We can list out the divisors by thinking through the numbers we might divide by. Then we can compare the lists to find common divisors, and choose the largest one.

The divisors of $a$ are 1, 2, 3, 4, 6, and 12.

The divisors of $b$ are 1, 2, 4, 5, 10, and 20.

The common divisors are 1, 2, and 4.

The greatest common divisor is 4.

An algorithm for finding the gcd

The definitions suggest one way to find $\text{gcd}(a,b)$ . We can retrace the steps in defining the gcd, computing what we can along the way. We first defined divisors, then common divisors, then finally the greatest common divisor. Following along in this way, we can do the following.

List out all of the divisors for $a$ .
List out all of the divisors for $b$ .
Compare the lists to find common divisors.
Select the biggest number from the list of common divisors.

Of course, we need to break these steps down into smaller problems. We can’t just look at the number $a$ and immediately write down its divisors. So we need to write out steps for building the list of divisors.

The simplest method for obtaining a list of divisors of $a$ is to start looking at all positive integers and check if they are a divisor according to the definition.

We’d like to know that we can stop checking numbers at some point. Thankfully, we would notice quickly that there’s no point in checking numbers larger than $a$ , since for $d>a$ , the value of $a/d$ must be less than 1 and so not an integer.

So, we compute $a/d$ for each of 1, …, $a$ , and if $a/d$ is an integer, then we record that $d$ is a divisor of $a$ . We can similarly get a list of divisors of $b$ .

Here is some Python code implementing the algorithm.

def gcd_1(a,b):
    divisors_a = []
    divisors_b = []
    for d in range(1,a+1):
        if a%d == 0:
            divisors_a.append(d)
    for d in range(1,b+1):
        if b%d == 0:
            divisors_b.append(d)
    common = []
    for d in divisors_a:
        if d in divisors_b:
            common.append(d)
    return max(common)

This is a very inefficient method, as we’ll see.

How slow is it?

Let’s think about how long this algorithm takes.

How long does step 1 (finding divisors of $a$ ) take? That is, if someone hands us an integer $a$ , how many numbers do we have to check to find all of the divisors of $a$ ? The simple method for listing divisors involves looking at each integer $d$ from 1 to $a$ and seeing if it is a divisor of $a$ . Each of these checks requires computing $a/d$ to see if it is an integer. This is $a$ many steps, each involving a division computation.

Similarly, step 2 (finding divisors of $b$ ) would take $b$ many steps of dividing $b$ by a number.

How long does step 3 (finding common divisors) take? Once we have the lists, we need to look over them to see what they have in common. Even for very large numbers, these lists will be very short compared to the size of $a$ and $b$ (See: growth rate of the divisor function), so we will just ignore this step.

Similarly, step 4 is just a matter of choosing the largest number in our last list, so we will ignore it for our discussion.

So, the algorithm above spends most of its time finding the divisors of $a$ and $b$ , and this takes about $a+b$ many little steps, each involving division.

For example, computing the gcd of numbers near 10000 would take us around 20000 steps if we use the above algorithm.

We want to speed things up.

Properties of divisors

The basic idea behind improving any algorithm is to take advantage of some extra structure available to us. That is, we want to make use of whatever symmetries, properties, assumptions, or byproducts of our work that we can use to cut down our ongoing work.

So, let’s think about properties of $\text{gcd}(a,b)$ by thinking back to the definitions we started with.

One of the easiest things to notice, if we start checking for divisors, is that the divisors of $a$ always include 1 and $a$ , but otherwise are all under $a/2$ . This is a property of divisors other than $a$ itself. It is impossible for any $d$ with $d > \frac{a}{2}$ to have remainder 0 when computing $a/d$ .

Moreover, we might notice during computation, or from the definition of divisors, that divisors generally come in pairs. When $d$ is a divisor of $a$ , we know that $a = d\cdot n$ for some integer $n$ . But this also means that $n$ is a divisor of $a$ .

So any divisor $d$ determines another divisor $n = a/d$ , which is a different number unless $a = d \cdot d$ .

If we think about this a bit more, we can see that when $a = d\cdot n$ , it is impossible for both of $d$ and $n$ to be smaller than $\sqrt{a}$ or larger than $\sqrt{a}$ , because these would make $d\cdot n < a$ or $d\cdot n > a$ . So at least one of the divisors from the pair must be under $\sqrt{a}$ .

This means we can actually get away with only checking for divisors by looking at numbers between 1 and $\sqrt{a}$ , as long as we remember to take the divisors in pairs.

Here is the Python implementation after being updated with these observations in mind.

def gcd_2(a,b):
    divisors_a = [1,a]
    divisors_b = [1,b]
    for d in range(2,int(a**(0.5))+1):
        if a%d == 0:
            divisors_a.append(d)
            divisors_a.append(a/d) #unnecessary when a=dd
    for d in range(2,int(b**(0.5))+1):
        if b%d == 0:
            divisors_b.append(d)
            divisors_b.append(b/d) #unnecessary when a=dd
    common = []
    for d in divisors_a:
        if d in divisors_b:
            common.append(d)
    return max(common)

This lets us drop down to about $\sqrt{a} + \sqrt{b}$ many steps, which is much better than the original algorithm. To compare, computing the gcd of numbers near 10000 would take us around 200 steps if we use this updated algorithm.

Properties of common divisors, gcd

Let’s look for other properties we can take advantage of and see if we get any other algorithms.

One of the first things we can notice is that $\text{gcd}(a,b) = \text{gcd}(b,a)$ . The gcd of $a$ and $b$ is the same as the gcd of $b$ and $a$ . This might sound silly to point out, but it’s a form of symmetry and worth noticing.

Does knowing $\text{gcd}(a,b)$ help us compute the gcd of any other values?

It doesn’t seem to help compute something like $\text{gcd}(a+1,b)$ , because it’s not immediately clear how the divisors of $a+1$ relate to the divisors of $b$ . We could see that $a$ and $a+1$ have no divisors in common, and so the common divisors of $a+1$ and $b$ have to be different from those of $a$ and $b$ . This might be a productive idea to follow, but it isn’t obvious where to go with this.

More general addition (or subtraction) like $\text{gcd}(a+n,b)$ or $\text{gcd}(a+n,b+n)$ also seems difficult to understand.

Simplification via division

However, if the inputs are multiplied by something, things are a bit easier to understand. This isn’t too surprising, since gcd is defined in terms of divisors, a notion related to division and multiplication.

If we know $\text{gcd}(a,b)$ , then we also know $\text{gcd}(n\cdot a,n\cdot b)$ for any $n$ , because this multiplication can be thought of as multiplying all of the common divisors by $n$ . The relation is the following equation.

$\text{gcd}(n\cdot a,n\cdot b) = n\cdot \text{gcd}(a,b)$

It might not be obvious, but one way to use this equation is to simplify a gcd by making the inputs smaller.

This is what happens if we use the equation to go from its left side to its right side. We can reduce the problem to computing a smaller gcd, and then multiplying by the $n$ we left behind.

When we have a common divisor $d$ of $a$ and $b$ , we can find integers $a'$ and $b'$ such that the following equations hold.

$\begin{matrix} a & = & d\cdot a' \\ b & = & d \cdot b' \end{matrix}$

We got these equations from the definition of $d$ being a divisor of both numbers. Notice that $a'\leq a$ and $b'\leq b$ must be true.

The gcd equation above lets us write the following (we use it for the rightmost =).

$\text{gcd}(a,b)=\text{gcd}(d\cdot a',d\cdot b') = d\cdot \text{gcd}(a',b')$

What if $d$ is a divisor of $a$ but not a divisor of $b$ ? In general, this doesn’t help much. There isn’t always a nice relation between $\text{gcd}(d\cdot a',b)$ and $\text{gcd}(a',b)$ . However, if $d$ is prime, then we can simplify things.

Suppose $d$ is a prime number which is a divisor of $a$ but not a divisor of $b$ . Then we can write $a = d\cdot a'$ , and we have the following equation.

$\text{gcd}(d\cdot a', b) = \text{gcd}(a', b)$

Notice that we don’t need to multiply either gcd by $d$ in this case. This equation holds because $d$ is prime and can’t be part of any divisor of $b$ if it doesn’t divide $b$ itself. This means the set of common divisors is unchanged when we divide $a$ by $d$ .

This equation doesn’t work when $d$ is not prime because it could then share divisors with $b$ . For example, 4 divides 12 but not 10, but gcd(12,10) = 2, while gcd(3, 10) = 1. In this example, dividing 12 by 4 removes the 2 divisor that was shared with 10.

Simplification via subtraction

The equations we get when we write out what it means for $d$ to be a common divisor also help us notice something about addition and subtraction that we might have missed.

If $d$ is a common divisor of our numbers, then $d$ is also a divisor of $a+b$ and also of $a-b$ and $b-a$ . This is easier to see when we’ve written $a = d\cdot a'$ and $b = d\cdot b'$ . For example, we can see how $d$ factors out of $a-b$ as follows.

$a-b = d\cdot a' - d\cdot b' = d\cdot (a' - b')$

This is notable because it means that whatever common divisors $a$ and $b$ have, $a-b$ also has as divisors. Exploring this idea more (and doing some more algebra) shows that common divisors of $a-b$ and $b$ will be divisors of $a$ . This combination of facts lets us write the following equation.

$\text{gcd}(a,b) = \text{gcd}(a-b, b)$

By working some more, or being clever with our earlier observation about the order of $a$ and $b$ , we can also get the following.

$\text{gcd}(a,b) = \text{gcd}(a, b-a)$

These equations are interesting because they reduce our problem (which is about divisors) using the operation of subtraction, which is simpler than multiplication or division.

The euclidean algorithm

The basic idea of the euclidean algorithm is to repeatedly use the equations we just saw that involve subtraction. By repeatedly subtracting the smaller of $a$ or $b$ from the larger, we can apply the equations above to reduce the computation of $\text{gcd}(a,b)$ to a gcd of small values.

In fact, as long as we always subtract the smaller from the larger, we will eventually be left with two equal numbers. That number will be the gcd of our original pair $(a,b)$ . This happens because of the equations above and the fact that we are always working with positive integers.

For example, say we want to compute the gcd of 999 and 1008. We will repeatedly subtract the smaller from the larger to reduce the problem. We’ll start working below.

gcd(999, 1008) =
gcd(999, 9) =
gcd(990, 9) =
gcd(981, 9) =
...

It’s clear that we’re going to be subtracting 9 for a while. Eventually, we will have subtracted some large multiple of 9.

Thinking about this a bit shows that what we’re ultimately doing is replacing the larger value with its remainder after division by the smaller value. That is, if $a$ is larger than $b$ , then we are saying that $\text{gcd}(a,b)$ is equal to $\text{gcd}(r,b)$ where $r$ is the remainder when we divide $a$ by $b$ .

$\text{gcd}(a,b) = \text{gcd}(r,b)$

We can think of this as a trick to simplify our algorithm by replacing a large number of subtractions with a division step. If we’re working by hand, this speed things up considerably.

Working the example above with this in mind:

gcd(999, 1008) =
gcd(999, 9) =
gcd(0, 9)

Now, gcd(0,9) is just 9, because everything is a divisor of 0. Alternatively, notice that the last steps if we were still doing subtraction would have been

... =
gcd(18,9) =
gcd(9,9) =
gcd(0,9)

and gcd(9,9) is easily computed to be 9.

This algorithm is generally much faster than the simple one we described at the start of the post, even if we restrict ourselves to subtraction. If we view it in terms of steps of division however, when $b$ is the smaller input, the euclidean algorithm is known to take at most $5\log_{10}(b)$ many division steps, or roughly 5 times the number of digits in $b$ . This is far less than the $\sqrt{a} + \sqrt{b}$ from earlier.

Here is a Python implementation, using only subtraction. Rather than alternate subtracting one side from the other, this code swaps the values of $a$ and $b$ whenever we ever end up with $a < b$ . This means that we end up with the gcd held in the position of $a$ at the end.

def euclidean_gcd(a,b):
    if a < b:
        a,b = b,a
    while b != 0:
        while a >= b:
            a -= b
        a,b = b,a
    return a

The binary gcd algorithm

The last algorithm we’ll discuss is one that makes use of the equations we saw when discussing simplification via division.

As a reminder, whenever $d$ is a divisor of both $a$ and $b$ , we have

$\text{gcd}(a,b)=\text{gcd}(d\cdot a',d\cdot b') = d\cdot \text{gcd}(a',b')$

and whenever $d$ is prime and is a divisor of $a$ but not of $b$ , we have

$\text{gcd}(d\cdot a', b) = \text{gcd}(a', b)$

The basic idea of the binary gcd algorithm is to repeatedly use these equations with $d=2$ . We can think of this as opportunistically carrying out the euclidean algorithm, but dividing by 2 whenever possible, using the equations above. We just need to remember that the first equation requires that we keep track of each copy of 2 we divide out, so that we can multiply our final gcd by them.

One of the motivations of this algorithm is that all of the needed operations with 2 can be carried out by shifting bits, which tends to be faster than typical multiplication and division.

Here is a Python implementation. It starts by removing as many shared 2 divisors as possible from $a$ and $b$ , creating a multiplier to adjust our gcd in the end. It continues removing (non-shared) 2 divisors from $a$ to make it odd. Then it enters a loop where it repeatedly makes $b$ odd and performs one subtraction, which creates an even value which is kept in the $b$ position. Because it finishes with $b=0$ and only makes use of the equations we discussed earlier, we are left with the gcd we want in the $a$ position, after adjusting by our multiplier.

def binary_gcd(a,b):
    multiplier = 0
    while a&1 == 0: #a is even
        a >>= 1 # divide by 2
        if b&1 == 0: # both were even
            b >>= 1
            multiplier += 1 # tally the shared 2
    while b != 0:
        while b&1 == 0:
            b >>= 1
        if a > b:
            a,b = b,a
        b -= a #subtract the smaller, b is even now
    return a << multiplier

Summary

We started with the definitions of divisors, common divisors, and greatest common divisors. We used these to describe a very simple algorithm for computing the gcd of two numbers. Then we discussed several properties of these objects and how we could use them to improve our algorithm. We were led to the euclidean algorithm and the binary gcd algorithm.