The greatest common divisor of two integers is the largest integer that evenly divides them both. For example, GCD(180, 105) = 15 because 15 is the largest integer that evenly divides into both 180 and 105.

Euclid's Elements c. 300 BC describes an efficient algorithm for calculating the GCD. The key idea is that the GCD of two numbers remains unchanged if you subtract the smaller from the larger.

The algorithm uses the fact that, if A >= B, then GCD(A, = GCD(B, A mod . To calculate the GCD, you simply repeat this operation until A mod B is zero, at which point the GCD is B. Here's the C# code:

// Use Euclid's algorithm to calculate the
// greatest common divisor (GCD) of two numbers.
private long GCD(long a, long b)
{
    // Make a >= b.
    a = Math.Abs(a);
    b = Math.Abs(b);
    if (a < b)
    {
        long tmp = a;
        a = b;
        b = tmp;
    }

    // Pull out remainders.
    for (; ; )
    {
        long remainder = a % b;
        if (remainder == 0) return b;
        a = b;
        b = remainder;
    };
}

The lest common multiple (LCM) of two integers A and B is the smallest integer that is a multiple of A and B. Calculating the LCM is easy with the GCD. Suppose A = a * g and B = b * g where g = GCD(A, and a and b are the other factors in A and B. Then LCM(A, = A * B / LCM(A, . Intuitively A * B contains two copies of the GCD (plus the other factors a and b) so you divide by the GCD to get the smallest multiple.

// Return the least common multiple
// (LCM) of two numbers.
private long LCM(long a, long b)
{
    return a * b / GCD(a, b);
}