Finding LCM Using GCD

What is the Least Common Multiple (LCM)?

The Least Common Multiple of two integers, a and b, is the smallest positive integer that is a multiple of both a and b.

For example, let's find the LCM of 15 and 20:

• Multiples of 15: 15, 30, 45, 60, 75, 90, ...
• Multiples of 20: 20, 40, 60, 80, 100, ...

The smallest number that appears in both lists is 60. Therefore, lcm(15, 20) = 60.

Just as with GCD, we could find this by generating multiples, but that's inefficient. Fortunately, there's a much more direct route if we already know the GCD.

The Fundamental Relationship Between GCD and LCM

There is a simple and powerful relationship connecting the GCD and LCM of any two positive integers a and b:

This means if we can calculate the GCD, we can find the LCM with simple arithmetic. By rearranging the formula, we get:

To understand why this is true, we can think about the prime factorization of the numbers, which we covered a few lessons ago.

• gcd(a, b) is formed by taking the minimum power of each prime factor common to a and b.
• lcm(a, b) is formed by taking the maximum power of each prime factor present in either a or b.

For any prime p, if a = p^x ... and b = p^y ..., then the power of p in gcd(a, b) is min(x, y) and in lcm(a, b) is max(x, y). It's a neat mathematical fact that for any two non-negative numbers x and y, x + y = min(x, y) + max(x, y). This relationship extends across all prime factors, leading directly to the formula gcd(a, b) * lcm(a, b) = a * b.

The following video provides a quick, intuitive explanation of this idea.

Implementing LCM: The Overflow Trap

With the formula lcm(a, b) = (a * b) / gcd(a, b), the C++ implementation seems trivial. However, there's a critical detail that's essential in competitive programming: integer overflow.

The USACO Guide, a fantastic resource for competitive programming training, clearly explains this issue.

As the guide points out, calculating a * b directly can easily exceed the capacity of a standard long long if a and b are large (e.g., 10^12). The product a * b might overflow before you get a chance to divide by the GCD.

The solution is to change the order of operations. Instead of (a * b) / gcd(a, b), we should compute it as:

a / gcd(a, b) * b

Since gcd(a, b) is, by definition, a divisor of a, the division a / gcd(a, b) results in an integer. This intermediate result is smaller than a, making the subsequent multiplication with b much less likely to overflow. The final lcm must still fit in your chosen data type, but this method avoids overflow on the intermediate calculation.

C++ Implementation

Here is a safe and robust way to implement LCM in C++, assuming you have the gcd function from our last lesson.

// Assumes a and b are non-negative.
// From the previous lesson:
long long gcd(long long a, long long b) {
    while (b) {
        a %= b;
        std::swap(a, b);
    }
    return a;
}

// Correct LCM implementation
long long lcm(long long a, long long b) {
    // LCM of 0 is 0. Avoid division by zero.
    if (a == 0 || b == 0) {
        return 0;
    }
    // To prevent overflow, we divide first.
    // Note that a and b must be of a type that can hold the result.
    return (a / gcd(a, b)) * b;
}

The image below provides a nice visual summary of the C++ code for both gcd and lcm, along with a dry run for gcd(15, 20) and lcm(15, 20).

Let's analyze the code in this image:

• The gcd function shown is return gcd(b % a, a); with the base case if (a == 0) return b;. This is a slightly different, but perfectly valid, recursive formulation compared to the one we saw last lesson. It demonstrates that the arguments can be swapped as long as the logic remains sound.
• The lcm function is return (a*b)/gcd(a, b);. As we just discussed, this is the version that is vulnerable to overflow! The dry run for lcm(15,20) works because 15 * 20 = 300, which is small. But if you tried lcm(1000000000, 1000000002), a*b would overflow a 64-bit integer, while our safe version (a / gcd(a,b)) * b would compute (1000000000 / 2) * 1000000002 and give the correct result. This image serves as a perfect example of what not to do in a competitive programming context where numbers can be large.

Conclusion

We have now completed our first module on core number theory. You've progressed from basic primality testing to understanding the intricate and useful relationship between GCD and LCM.

Here are the key takeaways from this lesson:

• The Least Common Multiple (LCM) is the smallest positive integer divisible by two numbers a and b.
• It's connected to the GCD by the fundamental formula: lcm(a, b) * gcd(a, b) = a * b.
• For efficient and safe computation, we use the rearranged formula: lcm(a, b) = (a / gcd(a, b)) * b.
• This specific order of operations is crucial to prevent integer overflow with large numbers, a vital consideration in competitive programming.
• Since C++17, you can use the built-in std::lcm function from the <numeric> header, which handles these issues for you. However, understanding the principle is essential for problem-solving and for working in environments with older C++ standards.

This completes our foundational block. You now have the tools to analyze the divisibility properties of integers. In our next lesson, we will begin a new module, Modular Arithmetic Operations. We'll dive into the world of "clock arithmetic," learning how to perform calculations that wrap around a modulus. This is one of the most important and frequently used concepts in all of competitive programming.