GCD and LCM Relationship

Number Theory · Axiom Academy

LESSON GCD and LCM Relationship Discover the beautiful connection between greatest common divisors and least common multiples through prime factorization For any two positive integers a and b , there exists a beautiful relationship between their greatest common divisor and least common multiple: This means that the product of the GCD and LCM of two numbers equals the product of the numbers themselves. Let's visualize this with an example. 2. Proof via Prime Factorization To understand why this relationship holds, we examine the prime factorizations of a and b . Consider any prime p that divides either number: In gcd( a, b ), the power of p is min(α, β) In lcm( a, b ), the power of p is max(α, β) The key insight is that for any two numbers α and β: This fundamental identity explains why the theorem works. When we multiply gcd( a, b ) × lcm( a, b ), each prime's total power is min(α, β) + max(α, β) = α + β, which is exactly the power in a × b . Rearranging our main theorem gives us an extremely useful computational formula. Since gcd( a, b ) × lcm( a, b ) = a × b , we can solve for the LCM: This formula is powerful because computing the GCD (using the Euclidean algorithm) is fast, while finding the LCM directly would require factorization. With this formula, we get the LCM "for free"! 5. Complete Example with Verification Let's compute lcm(48, 180) efficiently using our formula, then verify the relationship holds.

This is the written version of the interactive lesson above. See the full Number Theory course.