Applications: GCD and LCM via Prime Factorization
What you'll learn: How to compute the greatest common divisor and least common multiple of two numbers quickly using their prime factorizations.
The Core Idea
Once you have the prime factorizations of two numbers, finding their GCD and LCM becomes almost mechanical. Instead of running the Euclidean algorithm or listing all divisors, you can read off the answer directly from the exponents in the prime decompositions.
How It Works
Suppose you have two numbers with prime factorizations:
- a = p₁^e₁ · p₂^e₂ · p₃^e₃ · ...
- b = p₁^f₁ · p₂^f₂ · p₃^f₃ · ...
(where some exponents might be zero if a prime doesn't appear in one factorization)
For the GCD: Take the minimum exponent of each prime.
- GCD(a, b) = p₁^min(e₁,f₁) · p₂^min(e₂,f₂) · p₃^min(e₃,f₃) · ...
For the LCM: Take the maximum exponent of each prime.
- LCM(a, b) = p₁^max(e₁,f₁) · p₂^max(e₂,f₂) · p₃^max(e₃,f₃) · ...
Why This Works
Think of the GCD as the "largest number that divides both." It can only include primes that appear in both factorizations, and only as many times as the smaller count allows. Conversely, the LCM must be divisible by both numbers, so it needs enough of each prime to cover the larger requirement from either factorization.
Example
Let a = 72 = 2³ · 3² and b = 90 = 2¹ · 3² · 5¹.
- GCD(72, 90) = 2^min(3,1) · 3^min(2,2) · 5^min(0,1) = 2¹ · 3² · 5⁰ = 2 · 9 = 18
- LCM(72, 90) = 2^max(3,1) · 3^max(2,2) · 5^max(0,1) = 2³ · 3² · 5¹ = 8 · 9 · 5 = 360
Key Takeaway: Using prime factorizations, GCD is found by taking minimum exponents and LCM by taking maximum exponents—a direct, visual method that bypasses algorithmic computation.