GCD and LCM
“The greatest common divisor and least common multiple travel as a pair.”
The formula
GCD(a, b) × LCM(a, b) = a × bHow to read it: the greatest common divisor times the least common multiple equals the product of the two numbers
- GCD(a, b)
- — greatest common divisor — the largest number that divides both
- LCM(a, b)
- — least common multiple — the smallest number that is a multiple of both
- a × b
- — the product of the two numbers themselves
The hook
'The biggest number that divides both' and 'the smallest number both reach' — these two actually move as a pair.
In plain words
The GCD is the largest number dividing both; the LCM is the smallest number that is a multiple of both — the first place their multiples overlap.
The intuition
Prime factorization makes it clear. The GCD gathers only the primes both numbers share; the LCM gathers every prime that appears in either. That's why multiplying them gives back the product of the two numbers.
How it's built
12=2²×3, 18=2×3². Take only the shared minimum → GCD=2×3=6. Take the maximum of every prime → LCM=2²×3²=36. Check: 6×36=216=12×18.
Example
8 and 12: 8=2³, 12=2²×3. The shared part 2²=4 is the GCD. Generously taking all, 2³×3=24, is the LCM. And 4×24=96=8×12 checks out.
Common mistake
The GCD can't exceed the smaller number, and the LCM can't be less than the larger. Remembering GCD ≤ smaller ≤ larger ≤ LCM guards against mistakes.
Where it's used
Reducing fractions (GCD) and finding common denominators (LCM), when gears mesh up again, or splitting items evenly with none left over — real-life problems all use these.
Where it came from
'Euclid's algorithm' for quickly finding the GCD appears in the Elements around 300 BCE — the oldest algorithm still used by computers today.
Prerequisites
Quick check
What is the greatest common divisor of 12 and 18?
- 2
- 3
- 6✓
- 36
Practice
What is the GCD of 8 and 12?
Answer: 4
- 8 = 2³, 12 = 2² × 3
- Shared prime at its minimum: 2² = 4
Takeaway: The GCD takes only shared primes, at their minimum power.
What is the LCM of 4 and 6?
Answer: 12
- 4 = 2², 6 = 2 × 3
- Every prime at its maximum: 2² × 3 = 12
Takeaway: The LCM gathers every prime, at its maximum power.
What is the GCD of 15 and 25?
Answer: 5
- 15 = 3 × 5, 25 = 5²
- Shared prime: 5 → GCD = 5
Takeaway: If there's only one shared prime, that's the GCD.
Given that the GCD of 12 and 18 is 6, use GCD×LCM=a×b to find the LCM.
Answer: undefined
- GCD × LCM = a × b → 6 × LCM = 12 × 18 = 216
- LCM = 216 ÷ 6
- LCM = 36
Takeaway: Once you know the GCD, one multiply-and-divide gives the LCM.