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