Course contentsShow
← Mathematics
Lesson 2727 of 3,12154. Number TheoryFree lesson

Applications: GCD and LCM via Prime Factorization

Compute greatest common divisors and least common multiples efficiently using prime factorizations.

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.