LCM and GCD: Definitions, Computations, and Relationship

With our recent proof of Euclid's Lemma, we have solidified the most critical property of prime numbers. This completes a logical chain we've been building: from the Division Algorithm, we derived the Euclidean Algorithm to find the GCD, which in turn gave us Bézout's Identity, the key to proving the lemma.

In this lesson, we will explore the final foundational concept in this module: the Least Common Multiple (LCM). While you are likely familiar with how to compute the LCM from your school curriculum, our focus will be on its formal properties and, most importantly, proving its deep and elegant connection to the Greatest Common Divisor. This will provide a fitting conclusion to our study of the basic structures of divisibility before we move on to prime factorization in full detail.

1. Defining the Least Common Multiple

Just as the GCD is the greatest among all common divisors, the LCM is the least among all common multiples. Let's formalize this.

[PDF] Mathematics in OI (I) - Hong Kong Olympiad in Informatics

This document from the Hong Kong Olympiad in Informatics training materials provides a concise, formal definition of the LCM.

On page 50, read the section titled Least Common Multiple (LCM) - Definition. Focus on the two key parts: the definition of a common multiple and the definition of the LCM as the smallest positive one. The notation [a,b] is also common in Olympiad literature.

The definition states that $lcm (a, b)$ is the smallest positive integer $m$ such that $a ∣ m$ and $b ∣ m$ . This seems straightforward, but this "least" property implies a much stronger structural role. Just as the GCD of $a$ and $b$ divides any other common divisor, the LCM has a parallel property.

Theorem: If $k$ is any common multiple of $a$ and $b$ , then $lcm (a, b) ∣ k$ .

This means the LCM is not just the smallest common multiple; it is a fundamental building block for all common multiples. The proof elegantly uses the Division Algorithm, the very first concept we studied.

[PDF] Mathematics in OI (I) - Hong Kong Olympiad in Informatics

The same document provides a clear proof of this fundamental property.

On page 51, read the proof for Property 1. Follow the argument carefully: it assumes a common multiple n and writes n = qm+r where m=\text{lcm}(a,b). The logic then shows that r must also be a common multiple. Since r < m, the only way this doesn't contradict the "least" nature of m is if r is zero, which proves the divisibility.

2. The Core Relationship: Connecting GCD and LCM

You have probably encountered the formula relating GCD and LCM. The central result of this lesson is to prove it rigorously. The formula is:

For any positive integers $a$ and $b$ ,

gcd (a, b) \cdot lcm (a, b) = ab

This identity is a beautiful expression of the duality between the GCD and LCM. One way to visualize this relationship is by thinking about the prime factors of the numbers involved.

This Venn diagram illustrates the relationship for numbers 24 and 45. The GCD is formed by the prime factors in the intersection (3), while the LCM is formed by the prime factors in the union (2 x 2 x 2 x 3 x 3 x 5). Multiplying them together effectively counts every prime factor twice—once for each number—giving the same result as multiplying the numbers directly.

Let's now move from this visual intuition to formal proofs.

3. Proving the Identity

A hallmark of a fundamental theorem is that it can often be proven in several distinct ways, each providing a different insight. We will explore two such proofs.

Proof 1: Using Divisibility and Coprime Integers

This proof builds directly upon the ideas of GCD and relative primality that we have been developing. It is a very clean, algebraic argument.

Easiest and most complex proof of gcd(a,b)×lcm(a,b)=ab.

This Math StackExchange answer by André Nicolas provides an excellent, self-contained proof.

Read the first answer on the page. The core logic is as follows: Define \text{gcd}(a,b) = d, and write a=da_0 and b=db_0, where \text{gcd}(a_0, b_0)=1. It then shows that any common multiple m of a and b must be divisible by da_0b_0. Pay attention to how it uses the fact that a_0 and b_0 are relatively prime to show that b_0 must divide k. This implies that the least common multiple must be exactly da_0b_0. The final result follows: \text{gcd}(a,b) \cdot \text{lcm}(a,b) = d \cdot (da_0b_0) = (da_0)(db_0) = ab.

This proof is powerful because it relies on nothing more than the definition of the GCD and the properties of coprime integers (a specific case of Euclid's Lemma, which we saw last lesson).

Proof 2: Using Prime Factorization

This is perhaps the most common and intuitive proof, and it connects directly to the upcoming module on the Fundamental Theorem of Arithmetic.

Let the prime factorization of $a$ and $b$ be:
$a = p_{1}^{e_{1}} p_{2}^{e_{2}} \dots p_{k}^{e_{k}}$
$b = p_{1}^{f_{1}} p_{2}^{f_{2}} \dots p_{k}^{f_{k}}$
(Here, some exponents $e_{i}$ or $f_{i}$ can be zero if a prime does not divide one of the numbers).

From the definitions of GCD and LCM in terms of prime factors:

$gcd (a, b) = p_{1}^{m i n (e_{1}, f_{1})} p_{2}^{m i n (e_{2}, f_{2})} \dots p_{k}^{m i n (e_{k}, f_{k})}$
$lcm (a, b) = p_{1}^{m a x (e_{1}, f_{1})} p_{2}^{m a x (e_{2}, f_{2})} \dots p_{k}^{m a x (e_{k}, f_{k})}$

Multiplying these two expressions together gives:
$gcd (a, b) \cdot lcm (a, b) = \prod_{i = 1}^{k} p_{i}^{m i n (e_{i}, f_{i}) + m a x (e_{i}, f_{i})}$

For any two real numbers $x$ and $y$ , it is always true that $min (x, y) + max (x, y) = x + y$ . Applying this to our exponents:
$min (e_{i}, f_{i}) + max (e_{i}, f_{i}) = e_{i} + f_{i}$
Therefore, the product becomes:
$\prod_{i = 1}^{k} p_{i}^{e_{i} + f_{i}} = (\prod_{i = 1}^{k} p_{i}^{e_{i}}) \cdot (\prod_{i = 1}^{k} p_{i}^{f_{i}}) = ab$
This completes the proof. The video below explains this exact idea.

Properties of GCD, LCM | PRMO 2022 | PRMO Preparation | Abhay Mahajan | VOS

This video from Vedantu Olympiad School discusses the property and hints at the prime factorization proof.

Watch the segment from this timestamp. The presenter, Abhay Mahajan, explains how the LCM takes the highest powers of the primes and the GCD takes the lowest powers, and that when you multiply them, you recover the product of the original numbers.

This method using prime exponents is so useful that there is a special notation for it, called p-adic valuation. You will study this in depth later in the course (Module 8), but seeing it now provides a glimpse of a powerful tool.

[PDF] Mathematics in OI (I) - Hong Kong Olympiad in Informatics

This document introduces p-adic valuation and uses it to provide an extremely concise proof of our identity. This is for exposure, as the topic will be covered formally later.

First, read the Definition of p-adic valuation, \nu_p(a), on page 115. It is simply the exponent of the prime p in the prime factorization of a. Then, look at the claims on page 117, which state: \nu_p(\text{gcd}(a, b)) = \min(\nu_p(a), \nu_p(b)) \nu_p(\text{lcm}(a, b)) = \max(\nu_p(a), \nu_p(b)) Finally, see how these are used on page 118 to give a very elegant proof of the identity. This is exactly the same logic as our second proof, just expressed in a more professional notation.

4. A Note on Generalization

A common trap is to assume that this identity generalizes neatly to more than two numbers. This is false. For three integers $a, b, c$ :

gcd (a, b, c) \cdot lcm (a, b, c) \neq = ab c

For example, let $a = 2, b = 4, c = 6$ .

$gcd (2, 4, 6) = 2$
$lcm (2, 4, 6) = 12$
$gcd \cdot lcm = 2 \cdot 12 = 24$
But $ab c = 2 \cdot 4 \cdot 6 = 48$ .

The relationship for three or more variables is more complex, as you saw hinted at in the USAMO problem at the end of the LINK video. This is a good reminder that in mathematics, we must be precise about the conditions under which a theorem holds.

Conclusion

This lesson officially concludes our foundational module. We have journeyed from the most basic axiom of integer division to the intricate, dual relationship between the Greatest Common Divisor and the Least Common Multiple.

Key Takeaways:

LCM Definition: The Least Common Multiple, $lcm (a, b)$ , is the smallest positive integer divisible by both $a$ and $b$ .
Fundamental Property: The LCM is a divisor of every other common multiple.
The GCD-LCM Identity: For any positive integers $a$ and $b$ , $gcd (a, b) \cdot lcm (a, b) = ab$ .
Proof Techniques: We proved this identity using two different but equally important perspectives: one based on divisibility and coprime factors, and another based on prime factorization.

You now have a solid theoretical toolkit for dealing with divisibility. In our next lesson, we will begin Module 2 by using the machinery we've built, especially Euclid's Lemma, to formally state and prove the Fundamental Theorem of Arithmetic. This will open the door to a vast range of problems related to the multiplicative structure of integers.

Recommended resources

1. Defining the Least Common Multiple

2. The Core Relationship: Connecting GCD and LCM

3. Proving the Identity

Proof 1: Using Divisibility and Coprime Integers

Proof 2: Using Prime Factorization

4. A Note on Generalization

Conclusion