GCD and LCM are foundational number theory concepts used in simplifying fractions, solving equations, and scheduling problems. Here are every method explained clearly.
Definitions
GCD (Greatest Common Divisor) — also called GCF (Greatest Common Factor) or HCF (Highest Common Factor) — is the largest positive integer that divides both numbers without a remainder.
LCM (Least Common Multiple) is the smallest positive integer that is divisible by both numbers.
GCD(a, b) × LCM(a, b) = a × b
This relationship means once you find one, you can calculate the other:
LCM(a, b) = (a × b) ÷ GCD(a, b)
Method 1: Prime Factorisation
Best for: Understanding, smaller numbers, multiple numbers at once.
Steps for GCD:
- Prime factorise each number
- Find common prime factors
- Multiply the lowest powers of common factors
Steps for LCM:
- Prime factorise each number
- Multiply the highest powers of all prime factors
Example: GCD and LCM of 36 and 48
Prime factorise:
- 36 = 2² × 3²
- 48 = 2⁴ × 3
GCD: Common factors are 2 and 3. Take lowest powers:
- GCD = 2² × 3¹ = 4 × 3 = 12
LCM: All factors. Take highest powers:
- LCM = 2⁴ × 3² = 16 × 9 = 144
Verify: 36 × 48 = 1,728 = 12 × 144 ✓
Method 2: The Euclidean Algorithm (GCD)
Best for: Larger numbers — far faster than factorisation.
The key insight: GCD(a, b) = GCD(b, a mod b), repeating until the remainder is 0.
GCD(a, b):
while b ≠ 0:
r = a mod b
a = b
b = r
return a
Example: GCD(252, 105)
| Step | a | b | r = a mod b |
|---|---|---|---|
| 1 | 252 | 105 | 42 |
| 2 | 105 | 42 | 21 |
| 3 | 42 | 21 | 0 |
GCD = 21 (last non-zero remainder)
Example: GCD(1071, 462)
| Step | a | b | r |
|---|---|---|---|
| 1 | 1071 | 462 | 147 |
| 2 | 462 | 147 | 21 |
| 3 | 147 | 21 | 0 |
GCD = 21
Method 3: Division/Ladder Method
Best for: Visual learners, finding both GCD and LCM simultaneously.
Divide both numbers by their smallest common prime factor repeatedly:
Example: GCD and LCM of 12 and 18
2 | 12 18
3 | 6 9
| 2 3
GCD = product of divisors used = 2 × 3 = 6 LCM = product of divisors × remaining numbers = 2 × 3 × 2 × 3 = 36
LCM for More Than Two Numbers
Example: LCM(4, 6, 10)
Prime factorise:
- 4 = 2²
- 6 = 2 × 3
- 10 = 2 × 5
Take highest power of each prime: 2² × 3 × 5 = 60
Verify: 60 ÷ 4 = 15 ✓, 60 ÷ 6 = 10 ✓, 60 ÷ 10 = 6 ✓
Real-World Applications
Simplifying fractions: Divide numerator and denominator by their GCD.
- 24/36: GCD(24,36) = 12 → 24/36 = 2/3
Adding fractions with different denominators: Find LCM of denominators.
- 1/4 + 1/6: LCM(4,6) = 12 → 3/12 + 2/12 = 5/12
Scheduling problems: "Two buses leave at the same time. One runs every 12 minutes, another every 18 minutes. When do they depart together again?"
- LCM(12, 18) = 36 → every 36 minutes
Cutting materials: "A board is 36 cm, another is 48 cm. What is the longest equal-length piece you can cut from both with no waste?"
- GCD(36, 48) = 12 cm
Quick Mental Checks
GCD is always ≤ the smaller number LCM is always ≥ the larger number If GCD(a,b) = 1, the numbers are coprime — LCM(a,b) = a × b
Example: GCD(7, 13) = 1 (both prime, no common factors) → LCM = 7 × 13 = 91