HCF and LCM are two of the most fundamental concepts in aptitude. They show up directly in word problems (bells, circular tracks, tiles) and indirectly in fractions, ratios, and number theory questions. Let’s nail them down.
What Are HCF and LCM?
HCF (Highest Common Factor) — also called GCD (Greatest Common Divisor). It’s the largest number that divides two or more numbers evenly.
In simple language, HCF is the biggest number that “fits into” all the given numbers.
LCM (Lowest Common Multiple) — the smallest number that is a multiple of two or more numbers.
In simple language, LCM is the smallest number that all the given numbers “fit into.”
Example: For 12 and 18:
- Factors of 12: 1, 2, 3, 4, 6, 12
- Factors of 18: 1, 2, 3, 6, 9, 18
- Common factors: 1, 2, 3, 6 → HCF = 6
- Multiples of 12: 12, 24, 36, 48…
- Multiples of 18: 18, 36, 54…
- Common multiples: 36, 72… → LCM = 36
Methods to Find HCF
Method 1: Prime Factorization
- Find the prime factorization of each number
- Take the lowest power of all common primes
Example: HCF of 48 and 180
- 48 = 2⁴ × 3¹
- 180 = 2² × 3² × 5¹
- Common primes: 2 and 3
- Take lowest powers: 2² × 3¹ = 4 × 3 = 12
Method 2: Long Division (Euclid’s Algorithm)
This is faster for large numbers. Divide the larger number by the smaller. Then divide the divisor by the remainder. Keep going until the remainder is 0. The last divisor is the HCF.
Example: HCF of 462 and 198
- 462 ÷ 198 = 2 remainder 66
- 198 ÷ 66 = 3 remainder 0
- HCF = 66
This method is super clean — no prime factorization needed. Use it when numbers are large.
Methods to Find LCM
Method 1: Prime Factorization
- Find the prime factorization of each number
- Take the highest power of all primes (not just common ones)
Example: LCM of 48 and 180
- 48 = 2⁴ × 3¹
- 180 = 2² × 3² × 5¹
- Take highest powers: 2⁴ × 3² × 5¹ = 16 × 9 × 5 = 720
Method 2: Division Method
Write all numbers in a row. Divide by the smallest prime that divides at least one number. Bring down numbers that aren’t divisible. Keep going until all numbers become 1. Multiply all the divisors.
Example: LCM of 12, 15, and 20
| Divisor | Numbers |
|---|---|
| 2 | 12, 15, 20 |
| 2 | 6, 15, 10 |
| 3 | 3, 15, 5 |
| 5 | 1, 5, 5 |
| 5 | 1, 1, 1 |
LCM = 2 × 2 × 3 × 5 × 5 = 300
The Golden Relationship
LCM of fractions = LCM of numerators / HCF of denominators
Important: The HCF × LCM = Product formula works ONLY for two numbers. For three or more numbers, we can’t directly use this.
HCF and LCM of Fractions
Example: Find HCF and LCM of 2/3, 4/5, and 6/7.
HCF = HCF(2, 4, 6) / LCM(3, 5, 7) = 2 / 105 = 2/105
LCM = LCM(2, 4, 6) / HCF(3, 5, 7) = 12 / 1 = 12
Key Properties
- HCF of any two consecutive numbers is always 1 (they’re co-prime)
- LCM of any two consecutive numbers is always their product
- HCF always divides LCM
- HCF ≤ smaller number ≤ larger number ≤ LCM
- If HCF(a, b) = a, then a divides b (so LCM = b)
Worked Examples
Example 1: Basic application of the golden formula
The HCF of two numbers is 12 and their LCM is 360. If one number is 60, find the other.
HCF × LCM = Product of two numbers 12 × 360 = 60 × other number Other number = (12 × 360) / 60 = 4320 / 60 = 72
Example 2: The bells problem (classic!)
Three bells ring at intervals of 6, 8, and 12 minutes. If they ring together at 12:00, when will they ring together again?
They’ll ring together after LCM(6, 8, 12) minutes.
- 6 = 2 × 3
- 8 = 2³
- 12 = 2² × 3
- LCM = 2³ × 3 = 24 minutes
They ring together again at 12:24 PM.
Example 3: The tiles problem
A room is 12m × 8m. We want to tile it with the largest possible square tiles. What’s the side length of each tile, and how many tiles do we need?
Side of largest square tile = HCF(12, 8) = 4m Number of tiles = (12 × 8) / (4 × 4) = 96 / 16 = 6 tiles
Example 4: Finding numbers from HCF and LCM
The HCF of two numbers is 6. Their LCM is 180. If one number is between 30 and 50, find both numbers.
Since HCF = 6, both numbers are multiples of 6. Let numbers = 6a and 6b where HCF(a, b) = 1.
- LCM = 6 × a × b = 180 → a × b = 30
- Co-prime pairs with product 30: (1, 30), (2, 15), (3, 10), (5, 6)
- Numbers: (6, 180), (12, 90), (18, 60), (30, 36)
- One number between 30 and 50: The pair (30, 36) or (36, 30). Also possible: (18, 60) if we consider 18 isn’t in range but 60 is… re-read the question. If “one number” is between 30-50: 36 and the other is 30.
Example 5: Circular track problem
Two runners start at the same point on a circular track. Runner A completes a lap in 6 minutes, Runner B in 10 minutes. After how many minutes will they meet at the starting point again?
Time = LCM(6, 10) = 30 minutes
Common Exam Variations
- “Find the largest number that divides X and Y leaving remainders r₁ and r₂” → HCF(X - r₁, Y - r₂)
- “Find the largest number that divides X, Y, Z leaving the same remainder” → HCF(X-Y, Y-Z, X-Z) — take differences, then find HCF
- “N bells ring at intervals…” → LCM of all intervals
- “Largest square tile for a rectangle” → HCF of length and width
- “Two numbers given HCF and LCM” → Use HCF × LCM = product, and numbers = HCF × co-prime factors
Practice Problems
Q1: Find the greatest number that divides 65 and 117 leaving remainders 1 and 2 respectively.
Q2: Three traffic lights blink at intervals of 48 seconds, 72 seconds, and 108 seconds. If they blink together at 8:00 AM, when will they blink together again?
Q3: The HCF and LCM of two numbers are 8 and 480 respectively. If one number is 96, find the other.
Answers:
A1: We need HCF(65-1, 117-2) = HCF(64, 115). Using Euclid: 115 = 1×64 + 51, 64 = 1×51 + 13, 51 = 3×13 + 12, 13 = 1×12 + 1, 12 = 12×1. So HCF = 1. Hmm, let’s recheck: HCF(64, 115). 64 = 2⁶, 115 = 5 × 23. No common factors. HCF = 1.
A2: LCM(48, 72, 108). 48 = 2⁴ × 3, 72 = 2³ × 3², 108 = 2² × 3³. LCM = 2⁴ × 3³ = 16 × 27 = 432 seconds = 7 minutes 12 seconds. They blink together at 8:07:12 AM.
A3: HCF × LCM = a × b → 8 × 480 = 96 × b → b = 3840/96 = 40