9. Least common multiples

Once you know how to calculate GCDs, calculating LCMs is easy. To see why, suppose g = GCD(a, b). Then a = g × A and b = g × B for some integers A and B. In that case, LCM(a, b) is given by g × A × B.

You could divide a and b by g to find A and B, but you don't really need to know A and B. Instead, you can simply calculate LCM(a, b) = a × b/g. If you replace a and b in that equation with g × A and g × B, you get (g × A) × (g × B)/g. Canceling and rearranging a bit gives g × A × B, which is LCM(a, b).

That gives us the following simple method for calculating LCMs:

// Find LCM(a, b).
private long LCM(long a, long b)
{
    return a * b / GCD(a, b);
}

This method has one drawback. In the mathematical expression, the * and / operators have the same precedence, so the program evaluates them in left-to-right order. That means that it first calculates a * b and then divides that result by g. If a * b is too large, it will cause integer overflow. In particular, if you try to use this method to calculate LCM(1234567000, 7654321000), as required by this problem, the result is -8,996,971,959,702,551, which is clearly incorrect.

You can reduce this problem by making two modifications. First, use the checked keyword to ensure that the program looks for overflow. Second, you can rearrange the calculation to keep the intermediate values as small as possible during the calculation.

The following code shows an improved version of this method:

// Find LCM(a, b).
private long LCM(long a, long b)
{
    return checked(a / GCD(a, b) * b);
}

Now, the method first divides a by GCD(a, b). We know that GCD(a, b) divides evenly into a because it is a divisor of a, so a / GCD(a, b) is an integer. (In fact, that value is the value A that I described earlier.) The method then multiplies that intermediate value by b. The result may still cause overflow if the LCM is too big, but at least the method won't overflow during an intermediate calculation.

This version of the method can verify that LCM(1234567000, 7654321000) = 9,449,772,114,007,000.

There are two lessons here. First, as in earlier problems, use the checked keyword if there is a chance that the program might cause integer overflow. This lets the program detect the problem rather than trying to continue with a nonsensical result.

The second lesson is that you can sometimes rearrange calculations to avoid integer overflow.

Download the LCM example solution to see additional details.