Greatest Common Divisor

Euclid’s Algorithm

The greatest common divisor of two non-zero integers is a great example to illustrate the power of loops. Everyone learns about the concept of a greatest common divisor when faced with a fraction that is not in reduced form.

Consider the fraction \(\frac{2}{4}\), which is the same as \(\frac{1}{2}\). The fraction \(\frac{2}{4}\) can be reduced, because the numerator and denominator both have greatest common factor of 2. That is, \(\frac{2}{4} = \frac{1 \cdot 2}{2 \cdot 2}\). So the factor of 2 can be canceled from both the numerator and the denominator.

Euclid (the mathematician from classic times and author of Elements) is credited with having come up with a clever algorithm for how to compute the greatest common divisor efficiently. It is written as follows, where \(a \bmod b\) means a % b in C#.

\[ \begin{align}\begin{aligned}gcd(a, b) = gcd(b, a \bmod b)\\gcd(a, 0) = a\end{aligned}\end{align} \]

It is common in mathematics to list functions as one or more cases. The way you read this is as follows:

  • In general, the greatest common divisor of a and b is the same as computing the greatest common divisor of b and the remainder of a divided by b.

  • In the case where b is zero, the result is a. This makes sense because a divides itself and 0.

To gain some appreciation of how the definition always allows you to compute the greatest common divisor, it is worthwhile to try it out for a couple of numbers where you know the greatest common divisor. For example, we already know that the greatest common divisor of 10 and 15 is 5. Let’s use Euclid’s method to verify this:

  • \(gcd(10, 15) = gcd(15, 10 \bmod 15) = gcd(15, 10)\)

  • \(gcd(15, 10) = gcd(10, 15 \bmod 10) = gcd(10, 5)\)

  • \(gcd(10, 5) = gcd(5, 10 \bmod 5) = gcd(5, 0)\)

  • \(gcd(5, 0) = 5\)

Notice that in the example above, the first number (10) was smaller than the second (15), and the first transformation just swapped the numbers, so the larger number was first. Thereafter the first number is always larger.

GCD “Brute Force” Method

Now that we’ve gotten the preliminaries out of the way and have a basic mathematical explanation for how to calculate the greatest common divisor, we’ll take a look at how to translate this into code using the machinery of while loops that you’ve recently learned.

The way GCD is formulated above is, indeed, the most clever way to calculate the greatest common divisor. Yet the way we learn about the greatest common divisor in elementary school (at least at first) is to learn how to factor the numbers a and b, often in a brute force way. So for example, when calculating the greatest common divisor of 10 and 15, we can immediately see it, because we know that both of these numbers are divisible by 5 (e.g. 5 * 2 = 10 and 5 * 3 = 15). So the greatest common divisor is 5.

But if we had something more tricky to do like 810 and 729, we might have to think a bit more.

Before we learn to find the factors of numbers, we will often just “try” numbers until we get the greatest common divisor. This sort of trial process can take place in a loop, where we start at 1 and end at min(a, b). Why the minimum? We know that none of the values after the minimum can divide both a and b (in integer division), because no larger number can divide a smaller positive number. The smaller number would be the (non-zero) remainder.

Now take a look at a basic version of GCD:

 1/// Return the greatest common divisor of positive numbers.
 2public static int GreatestCommonDivisor (int a, int b)
 3{
 4   int n = Math.Min (a, b);
 5   int gcd = 1, i = 1;
 6
 7   while (i <= n) {
 8      if (a % i == 0 && b % i == 0) {
 9         gcd = i;
10      }
11      i++;
12   }
13   return gcd;
14}

This code works as follows:

  • We begin by finding Math.Min(a, b). This is how to compute the minimum of any two values in C#. Technically, we don’t need to use the minimum of a and b, but there is no point in doing any more work than necessary.

  • We’ll use the variable i as the loop index, starting at 1.

  • The variable gcd will hold the largest currently known common divisor. We start with 1, which divides any integer, and we will look for a higher value that also divides a and b.

  • The line while (i <= n) is used to indicate that we are iterating the values of i until the minimum of a and b (computed earlier) is reached.

  • The line if (a % i == 0 && b % i == 0) is used to check whether we have found a new value that replaces our previous candidate for the GCD. A value can only be a candidate for the GCD if it divides a and b without a remainder. The modulus operator % is our way of determining whether there is a remainder from the division operation a / i or b / i.

  • The line i++ is our way of going to the next value of i to be tested as the new GCD.

  • When this loop terminates, the greatest common divisor has been found.

So this gives you a relatively straightforward way of calculating the greatest common divisor. While simple, it is not necessarily the most efficient way of determining the GCD. If you think about what is going on, this loop could run a significant number of times. For example, if you were calculating the GCD two very large numbers, say, one billion (1,000,000,000) and two billion (2,000,000,000) it is painfully evident that you would consider a large number of values (a billion, in fact) before obtaining the candidate GCD, which we know is 1,000,000,000.

Brute-Force GCD Exercise

The code above goes though all integers 2 through min(a, b). That is not generally necessary when the GCD is greater than 1, even with a brute-force mindset. Write a g_c_d_basic_faster.cs to do this with a slightly different GreatestCommonDivisor function. 1

GCD Subtraction Method

The subtraction method (also attributable to Euclid) to compute the Greatest Common Divisor works as follows:

  • Based on the mathematical definition in the previous section, the greatest common divisor algorithm saves a step when we already have a and b in the right order.

  • The right order means that \(a > b\). As we noted earlier, the cleverness of the mathematical definition is that a and b are swapped as the first step to ensure that \(a > b\), after which we can repeatedly divide to get the GCD.

  • Division, of course, is a form of repetitive subtraction, so the way to divide by b is to repeatedly subtract it (from a) until a is no longer greater than b.

  • The subtraction method basically makes no attempt to put a and b in the right order. Instead, we just write similar loops to allow for the possibility of either order.

  • A simple check must be performed to ensure that the approach of repeated subtraction actually resulted in the GCD. This will happen if a and b bump into one another, thereby meaning that we have computed the GCD.

 1public static int GreatestCommonDivisor (int a, int b)
 2{
 3   int c;
 4   while (a != b) {
 5      while (a > b) {
 6         c = a - b;
 7         a = c;
 8      }
 9      while (b > a) {
10         c = b - a;
11         b = c;
12      }
13   }
14   return a;
15}

A look at the source code more or less follows the above explanation.

Let’s start by looking at the inner loop at line 5, while (a > b). In this loop, we are repeatedly subtracting b from a, which we know we can do, because a started out as being larger than b. At the end of loop a is reduced to either

  1. b, in which case b exactly divided the earlier a, and b is the GCD, or

  2. a number less than b, namely \(a \bmod b\) (or in C# terms a % b), and the process continues….

The loop on line 9 is similar to the loop in line 5. For the same reasons as we already explained, b ends up equal to a, which is the GCD, or b ends up as \(b \bmod a\).

As discussed above, if a and b end up as the same number, that is the GCD. On the other hand, the first GCD algorithm example showed how remainders may need to be to be calculated over and over. The outer loop in this version keeps this up until a and b are reduced to equal values. At this point the inner loops would make no further changes, and the common value is the GCD.

As an exercise to the reader, you may want to consider adding some Console.WriteLine() statements to print the values of a and b within each loop, and after both loops have executed. It will allow you to see in visual terms how this method does its work.

GCD Remainder Loop

There are several ways to code the shorter Euclidean algorithm at the beginning of this GCD section. It is a repetitive pattern, and a loop can be used. There are two parameters, a and b, to the gcd, and they can be successively changed, suggesting a loop. What is the continuation condition? You stop when b is 0, so you continue while b != 0. The parameters a and b need to be replaced by b and a % b. One extra variable needs to be introduced to make this double change work. The simplest is to introduce a variable r for the remainder. Check and see for yourself that you need an extra variable like r:

/// Return the greatest comon divisor of nonnegative numbers,
/// not both 0.
public static int GreatestCommonDivisor (int a, int b)
{
   while (b != 0) {
      int r = a % b;
      a = b;
      b = r;
   }
   return a;
}

More verbose demonstration code, that prints the progress each time through loop is in g_c_d_remainder_loop/g_c_d_remainder_loop.cs.

Preview: Recursive GCD

The first statement of Euclid’s algorithm said (in C#) when

gcd(a, b) = gcd(b, a % b)

It is saying the result of the function with one set of parameters is equal to calling the function with another set of parameters. If we put this into a C# function definition, it would mean the instructions for the function say to call itself. This is a broadly useful technique called recursion, where a function calls itself inside its definition. We don’t expect you to master this technique immediately but do feel that it is important you at least hear about it and see its tremendous power:

/// Return the greatest comon divisor of nonnegative numbers,
/// not both 0.
public static int GreatestCommonDivisor (int a, int b)
{
   if (b == 0) {                               // base
      return a;                                //   case
   } else {
      return GreatestCommonDivisor (b, a % b); // recursion
   }
}

  • Recalling our earlier definition, the case \(gcd(a, 0) = a\) is handled directly by lines commented as “base case”.

  • And the case \(gcd(a, b) = gcd(b, a \bmod b)\) is handled by line with comment “recursion”, with the function calling itself.

In g_c_d_euclid_recursive/g_c_d_euclid_recursive.cs is a wordier demonstration version that prints to the screen the progress at each recursive call.

The recursive version of the gcd function refers to itself by calling itself. Though this seems circular, you can see from the examples that it works very well. The important point is that the calls to the same function are not completely the same: Successive calls have smaller second numbers, and the second number eventually reaches 0, and in that case there is a direct final answer. Hence the function is not really circular.

This recursive version is a much more direct translation of the original mathematical algorithm than the looping version!

The general idea of recursion is for a function to call itself with simpler parameters, until a simple enough place is reached, where the answer can be directly calculated.

1

The original brute-force gcd approach always goes through all the integers between 1 and min(a, b). There is a way to stop the first time the real gcd is reached. How can you arrange that?