The greatest common divisor (GCD) of two or more integers is the largest positive integer that divides each of the numbers without leaving a remainder. For instance, the common divisors of 12 and 18 are 1, 2, 3, and 6. The largest among them is 6, so gcd(12, 18) = 6. This concept is fundamental in areas like cryptography, fraction simplification, and scheduling problems.

Iterative Approach to Finding GCD

A straightforward method to compute the GCD of two numbers is to test all integers up to the smaller number and find the largest common divisor.

int findGCD(int x, int y) {
    int greatestDivisor = 1;
    int limit = (x < y) ? x : y;
    for (int divisor = 2; divisor <= limit; divisor++) {
        if (x % divisor == 0 && y % divisor == 0) {
            greatestDivisor = divisor;
        }
    }
    return greatestDivisor;
}

While simple, this method is inefficient, especially for large numbers or coprime pairs (where the GCD is 1), resulting in O(n) time complexity.

The Euclidean Algorithm

Attributed to the ancient Greek mathematician Euclid, this algorithm provides a far more efficient way to compute the GCD. It is based on the principle that the GCD of two numbers also divides their difference. The core recursive relationship is:

[ \text{gcd}(a, b) = \text{gcd}(b, a \bmod b) ]

with the base case: [ \text{gcd}(a, 0) = a ]

This leads to a concise recursive implementation:

int gcdRecursive(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gcdRecursive(b, a % b);
}

The algorithm can also be implemented itreatively, which is often preferred to avoid stack overflow for very large numbers.

int gcdIterative(int a, int b) {
    int remainder;
    while (b != 0) {
        remainder = a % b;
        a = b;
        b = remainder;
    }
    return a;
}

Proof of Correctness and Termination

The algorithm's termination is guaranteed because the second argument b strictly decreases in each recursive or iterative step (since a % b is always less than b for positive b). It must eventually reach zero.

Its correctness stems from the mathematical property: if a number d divides both a and b, then it also divides their difference a - b and, by extension, the remainder a % b. Therefore, the set of common divisors of (a, b) is identical to the set of common divisors of (b, a % b). Consequently, their greatest common divisor is the same.

Formally, let a = m * d and b = n * d. Then a % b = a - k * b = (m - k * n) * d, which is also divisible by d. This invariant ensures the algorithm correctly preserves the GCD throughout its computation.