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 , the divisors of are the positive integers such that divided by has remainder 0. In other words, is a divisor of if the value of is an integer.
Yet another way to say this is that is a divisor of if we can find some integer such that
If we have another integer , we can ask whether is also a divisor of . Maybe is a divisor of both. That is, and could both be integers (even if they are different integers).
Given two integers and , a common divisor of and is any integer which is a divisor of both and . At least one common divisor will exist, because both and have the number 1 as a divisor.
The greatest common divisor of and is the biggest integer we can find among the list of common divisors of and .
Let and . 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 are 1, 2, 3, 4, 6, and 12.
The divisors of 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 . 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 .
- List out all of the divisors for .
- 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 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 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 , since for , the value of must be less than 1 and so not an integer.
So, we compute for each of 1, …, , and if is an integer, then we record that is a divisor of . We can similarly get a list of divisors of .
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 ) take? That is, if someone hands us an integer , how many numbers do we have to check to find all of the divisors of ? The simple method for listing divisors involves looking at each integer from 1 to and seeing if it is a divisor of . Each of these checks requires computing to see if it is an integer. This is many steps, each involving a division computation.
Similarly, step 2 (finding divisors of ) would take many steps of dividing 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 and (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 and , and this takes about 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 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 always include 1 and , but otherwise are all under . This is a property of divisors other than itself. It is impossible for any with to have remainder 0 when computing .
Moreover, we might notice during computation, or from the definition of divisors, that divisors generally come in pairs. When is a divisor of , we know that for some integer . But this also means that is a divisor of .
So any divisor determines another divisor , which is a different number unless .
If we think about this a bit more, we can see that when , it is impossible for both of and to be smaller than or larger than , because these would make or . So at least one of the divisors from the pair must be under .
This means we can actually get away with only checking for divisors by looking at numbers between 1 and , 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 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 . The gcd of and is the same as the gcd of and . This might sound silly to point out, but it’s a form of symmetry and worth noticing.
Does knowing help us compute the gcd of any other values?
It doesn’t seem to help compute something like , because it’s not immediately clear how the divisors of relate to the divisors of . We could see that and have no divisors in common, and so the common divisors of and have to be different from those of and . This might be a productive idea to follow, but it isn’t obvious where to go with this.
More general addition (or subtraction) like or 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 , then we also know for any , because this multiplication can be thought of as multiplying all of the common divisors by . The relation is the following equation.
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 we left behind.
When we have a common divisor of and , we can find integers and such that the following equations hold.
We got these equations from the definition of being a divisor of both numbers. Notice that and must be true.
The gcd equation above lets us write the following (we use it for the rightmost =).
What if is a divisor of but not a divisor of ? In general, this doesn’t help much. There isn’t always a nice relation between and . However, if is prime, then we can simplify things.
Suppose is a prime number which is a divisor of but not a divisor of . Then we can write , and we have the following equation.
Notice that we don’t need to multiply either gcd by in this case. This equation holds because is prime and can’t be part of any divisor of if it doesn’t divide itself. This means the set of common divisors is unchanged when we divide by .
This equation doesn’t work when is not prime because it could then share divisors with . 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 to be a common divisor also help us notice something about addition and subtraction that we might have missed.
If is a common divisor of our numbers, then is also a divisor of and also of and . This is easier to see when we’ve written and . For example, we can see how factors out of as follows.
This is notable because it means that whatever common divisors and have, also has as divisors. Exploring this idea more (and doing some more algebra) shows that common divisors of and will be divisors of . This combination of facts lets us write the following equation.
By working some more, or being clever with our earlier observation about the order of and , we can also get the following.
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 or from the larger, we can apply the equations above to reduce the computation of 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 . 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 is larger than , then we are saying that is equal to where is the remainder when we divide by .
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 is the smaller input, the euclidean algorithm is known to take at most many division steps, or roughly 5 times the number of digits in . This is far less than the 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 and whenever we ever end up with . This means that we end up with the gcd held in the position of 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 is a divisor of both and , we have
and whenever is prime and is a divisor of but not of , we have
The basic idea of the binary gcd algorithm is to repeatedly use these equations with . 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 and , creating a multiplier to adjust our gcd in the end. It continues removing (non-shared) 2 divisors from to make it odd. Then it enters a loop where it repeatedly makes odd and performs one subtraction, which creates an even value which is kept in the position. Because it finishes with and only makes use of the equations we discussed earlier, we are left with the gcd we want in the 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
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.