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#.

\[gcd(a, b) = gcd(b, a \bmod b)\]\[gcd(a, 0) = a\]

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.

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

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.

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.

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

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

`b`

, in which case`b`

exactly divided the earlier`a`

, and`b`

is the GCD, or- 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.

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.

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? |