Episode 8 — Aptitude and Reasoning / 8.7 — HCF and LCM
8.7.a Concepts and Formulas
1. Factors and Multiples -- A Quick Recap
Before diving into HCF and LCM, let us ensure the foundation is solid.
Factor (Divisor): A number a is a factor of b if b / a leaves no remainder.
Factors of 12: 1, 2, 3, 4, 6, 12
Factors of 18: 1, 2, 3, 6, 9, 18
Multiple: A number m is a multiple of a if m = a x k for some positive integer k.
Multiples of 4: 4, 8, 12, 16, 20, 24, 28, ...
Multiples of 6: 6, 12, 18, 24, 30, 36, ...
Common Factors of 12 and 18: 1, 2, 3, 6 Common Multiples of 4 and 6: 12, 24, 36, 48, ...
2. HCF -- Highest Common Factor
2.1 Definition
The Highest Common Factor (HCF) of two or more numbers is the largest number that divides each of them exactly (without leaving a remainder).
Other names: GCD (Greatest Common Divisor), GCF (Greatest Common Factor).
HCF(12, 18) = 6
Because:
Common factors of 12 and 18 = {1, 2, 3, 6}
Highest among them = 6
2.2 Method 1 -- Prime Factorization Method
Steps:
- Express each number as a product of prime factors.
- Identify the common prime factors.
- For each common prime factor, take the lowest power.
- Multiply them together.
Rule: HCF = Product of LOWEST powers of COMMON prime factors
Worked Example: Find HCF(48, 72)
Step 1: Prime factorization
48 = 2^4 x 3^1
72 = 2^3 x 3^2
Step 2: Common prime factors = 2 and 3
Step 3: Lowest powers
For 2: min(4, 3) = 3 --> 2^3
For 3: min(1, 2) = 1 --> 3^1
Step 4: HCF = 2^3 x 3^1 = 8 x 3 = 24
Verification: 48 / 24 = 2 (exact). 72 / 24 = 3 (exact). Correct.
Worked Example: Find HCF(60, 84, 108)
Step 1: Prime factorization
60 = 2^2 x 3^1 x 5^1
84 = 2^2 x 3^1 x 7^1
108 = 2^2 x 3^3
Step 2: Common prime factors = 2 and 3
(5 is not in 84 or 108; 7 is not in 60 or 108)
Step 3: Lowest powers
For 2: min(2, 2, 2) = 2 --> 2^2
For 3: min(1, 1, 3) = 1 --> 3^1
Step 4: HCF = 2^2 x 3^1 = 4 x 3 = 12
2.3 Method 2 -- Long Division Method (Successive Division)
This is practical when numbers are large and prime factorization is tedious.
Steps (for two numbers a and b, where a > b):
- Divide the larger number by the smaller number.
- If remainder = 0, the divisor is the HCF.
- If remainder is not 0, replace the larger number with the smaller number, and the smaller number with the remainder. Repeat.
Worked Example: Find HCF(462, 132)
Step 1: 462 / 132
462 = 132 x 3 + 66 Remainder = 66
Step 2: 132 / 66
132 = 66 x 2 + 0 Remainder = 0
Since remainder = 0, the divisor (66) is the HCF.
HCF(462, 132) = 66
Worked Example: Find HCF(1071, 462)
1071 = 462 x 2 + 147 Remainder = 147
462 = 147 x 3 + 21 Remainder = 21
147 = 21 x 7 + 0 Remainder = 0
HCF(1071, 462) = 21
2.4 Method 3 -- Euclidean Algorithm
The Euclidean Algorithm is essentially the same as the long division method, expressed more formally.
Algorithm: HCF(a, b)
If b = 0, return a
Else return HCF(b, a mod b)
Worked Example: HCF(270, 192)
HCF(270, 192) = HCF(192, 270 mod 192) = HCF(192, 78)
HCF(192, 78) = HCF(78, 192 mod 78) = HCF(78, 36)
HCF(78, 36) = HCF(36, 78 mod 36) = HCF(36, 6)
HCF(36, 6) = HCF(6, 36 mod 6) = HCF(6, 0)
HCF(6, 0) = 6
HCF(270, 192) = 6
2.5 HCF of Three or More Numbers
Compute the HCF of two numbers first, then find the HCF of that result with the next number.
HCF(a, b, c) = HCF(HCF(a, b), c)
Worked Example: Find HCF(36, 60, 84)
Step 1: HCF(36, 60)
36 = 2^2 x 3^2
60 = 2^2 x 3 x 5
HCF = 2^2 x 3 = 12
Step 2: HCF(12, 84)
12 = 2^2 x 3
84 = 2^2 x 3 x 7
HCF = 2^2 x 3 = 12
HCF(36, 60, 84) = 12
3. LCM -- Least Common Multiple
3.1 Definition
The Least Common Multiple (LCM) of two or more numbers is the smallest positive number that is exactly divisible by each of them.
LCM(4, 6) = 12
Because:
Multiples of 4: 4, 8, 12, 16, 20, 24, ...
Multiples of 6: 6, 12, 18, 24, 30, ...
Common multiples: 12, 24, 36, ...
Least among them = 12
3.2 Method 1 -- Prime Factorization Method
Steps:
- Express each number as a product of prime factors.
- List all prime factors that appear in any of the numbers.
- For each prime factor, take the highest power.
- Multiply them together.
Rule: LCM = Product of HIGHEST powers of ALL prime factors
Worked Example: Find LCM(48, 72)
Step 1: Prime factorization
48 = 2^4 x 3^1
72 = 2^3 x 3^2
Step 2: All prime factors = 2 and 3
Step 3: Highest powers
For 2: max(4, 3) = 4 --> 2^4
For 3: max(1, 2) = 2 --> 3^2
Step 4: LCM = 2^4 x 3^2 = 16 x 9 = 144
Worked Example: Find LCM(12, 15, 20)
Step 1: Prime factorization
12 = 2^2 x 3^1
15 = 3^1 x 5^1
20 = 2^2 x 5^1
Step 2: All prime factors = 2, 3, 5
Step 3: Highest powers
For 2: max(2, 0, 2) = 2 --> 2^2
For 3: max(1, 1, 0) = 1 --> 3^1
For 5: max(0, 1, 1) = 1 --> 5^1
Step 4: LCM = 2^2 x 3 x 5 = 4 x 3 x 5 = 60
3.3 Method 2 -- Common Division Method
This is a quick method, especially for three or more numbers.
Steps:
- Write all numbers in a row.
- Divide by the smallest prime that divides at least one number.
- Carry forward any number that is not divisible as-is.
- Continue until all numbers reduce to 1.
- LCM = Product of all the divisors used.
Worked Example: Find LCM(12, 15, 20)
2 | 12 15 20
2 | 6 15 10
3 | 3 15 5
5 | 1 5 5
| 1 1 1
LCM = 2 x 2 x 3 x 5 = 60
Worked Example: Find LCM(8, 12, 18, 24)
2 | 8 12 18 24
2 | 4 6 9 12
2 | 2 3 9 6
3 | 1 3 9 3
3 | 1 1 3 1
| 1 1 1 1
LCM = 2 x 2 x 2 x 3 x 3 = 72
3.4 LCM of Three or More Numbers
Like HCF, we can build up pairwise:
LCM(a, b, c) = LCM(LCM(a, b), c)
Or use the common division method directly (often faster for 3+ numbers).
4. The Fundamental Relationship: HCF x LCM = Product of Two Numbers
This is one of the most important formulas in this topic.
For any two positive integers a and b:
HCF(a, b) x LCM(a, b) = a x b
Rearrangements:
LCM(a, b) = (a x b) / HCF(a, b)
HCF(a, b) = (a x b) / LCM(a, b)
Worked Example: Verify for a = 12, b = 18
HCF(12, 18) = 6
LCM(12, 18) = 36
HCF x LCM = 6 x 36 = 216
a x b = 12 x 18 = 216
Verified: HCF x LCM = Product of the two numbers.
IMPORTANT: This formula works ONLY for exactly two numbers. For three or more numbers, the relationship does not hold directly. For three numbers:
LCM(a, b, c) != (a x b x c) / (HCF(a, b, c)) [INCORRECT!]
Worked Example: Using the formula to find LCM
The HCF of two numbers is 12 and their product is 2160. Find the LCM.
LCM = Product / HCF = 2160 / 12 = 180
5. HCF and LCM of Fractions
5.1 HCF of Fractions
HCF of fractions = HCF of numerators / LCM of denominators
Worked Example: Find HCF of 2/3, 4/9, 6/15
Numerators: 2, 4, 6 --> HCF(2, 4, 6) = 2
Denominators: 3, 9, 15 --> LCM(3, 9, 15) = 45
HCF = 2/45
5.2 LCM of Fractions
LCM of fractions = LCM of numerators / HCF of denominators
Worked Example: Find LCM of 2/3, 4/9, 6/15
Numerators: 2, 4, 6 --> LCM(2, 4, 6) = 12
Denominators: 3, 9, 15 --> HCF(3, 9, 15) = 3
LCM = 12/3 = 4
5.3 Verification
The HCF of fractions should divide each fraction exactly, and each fraction should divide the LCM exactly.
2/3 divided by 2/45 = (2/3) x (45/2) = 15 (integer, so HCF divides it)
4/9 divided by 2/45 = (4/9) x (45/2) = 10 (integer, correct)
6/15 divided by 2/45 = (6/15) x (45/2) = 9 (integer, correct)
4 divided by 2/3 = 4 x (3/2) = 6 (integer, so LCM is a multiple)
4 divided by 4/9 = 4 x (9/4) = 9 (integer, correct)
4 divided by 6/15 = 4 x (15/6) = 10 (integer, correct)
6. Properties of HCF and LCM
6.1 Basic Properties
Property 1: HCF(a, b) always divides both a and b.
Property 2: Both a and b always divide LCM(a, b).
Property 3: HCF(a, b) always divides LCM(a, b).
Property 4: HCF(a, b) <= min(a, b)
Property 5: LCM(a, b) >= max(a, b)
Property 6: If one number is a multiple of the other, say b = k*a, then:
HCF(a, b) = a (the smaller number)
LCM(a, b) = b (the larger number)
Property 7: If two numbers are co-prime (HCF = 1), then:
LCM(a, b) = a x b
6.2 Co-prime Numbers
Two numbers are co-prime (or relatively prime) if their HCF is 1.
Examples of co-prime pairs:
(8, 15) --> HCF = 1 (co-prime)
(14, 25) --> HCF = 1 (co-prime)
(9, 10) --> HCF = 1 (co-prime)
Note: Co-prime numbers need not be individually prime.
8 and 15 are co-prime, but neither 8 nor 15 is prime.
6.3 HCF and LCM of Consecutive Numbers
HCF of any two consecutive integers = 1 (always co-prime)
LCM of any two consecutive integers = their product
Example: HCF(14, 15) = 1, LCM(14, 15) = 210 = 14 x 15
6.4 Important Deductions
If HCF(a, b) = h, then:
a = h * x and b = h * y, where HCF(x, y) = 1
LCM(a, b) = h * x * y
This means: a / HCF and b / HCF are always co-prime.
Worked Example:
HCF of two numbers is 6 and their LCM is 180. One number is 36. Find the other.
Method 1 (using product formula):
a x b = HCF x LCM
36 x b = 6 x 180
36 x b = 1080
b = 1080 / 36 = 30
Method 2 (using the deduction):
a = 36 = 6 x 6, so x = 6
LCM = h x x x y = 6 x 6 x y = 180
y = 180 / 36 = 5
b = h x y = 6 x 5 = 30
Verification: HCF(36, 30) = 6, LCM(36, 30) = 180. Correct.
7. Finding Numbers Given HCF and LCM
This is a very common exam problem type.
7.1 Finding Two Numbers When HCF and LCM Are Known
Given: HCF = h, LCM = L
Step 1: L must be divisible by h. If not, no such pair exists.
Step 2: Let the numbers be h*x and h*y, where HCF(x, y) = 1.
Step 3: LCM = h * x * y, so x * y = L / h.
Step 4: Find co-prime pairs (x, y) whose product = L / h.
Step 5: The numbers are h*x and h*y.
Worked Example:
Find all pairs of numbers whose HCF is 4 and LCM is 240.
h = 4, L = 240
x * y = L / h = 240 / 4 = 60
Find co-prime pairs (x, y) with product 60:
60 = 1 x 60 --> HCF(1, 60) = 1 --> valid pair: (4, 240)
60 = 3 x 20 --> HCF(3, 20) = 1 --> valid pair: (12, 80)
60 = 4 x 15 --> HCF(4, 15) = 1 --> valid pair: (16, 60)
60 = 5 x 12 --> HCF(5, 12) = 1 --> valid pair: (20, 48)
60 = 2 x 30 --> HCF(2, 30) = 2 --> NOT co-prime, reject
60 = 6 x 10 --> HCF(6, 10) = 2 --> NOT co-prime, reject
Valid pairs: (4, 240), (12, 80), (16, 60), (20, 48)
7.2 Quick Check for Validity
For any two numbers a and b:
1. HCF must divide both numbers.
2. LCM must be a multiple of both numbers.
3. HCF must divide LCM.
4. HCF x LCM = a x b.
8. HCF and LCM in Word Problems -- Applications
8.1 Bells Ringing Together (LCM Problem)
When bells ring at different intervals, they ring together again after an interval equal to the LCM of the individual intervals.
Worked Example:
Three bells ring at intervals of 6, 8, and 12 minutes. If they ring together at 12:00 noon, when will they next ring together?
LCM(6, 8, 12):
6 = 2 x 3
8 = 2^3
12 = 2^2 x 3
LCM = 2^3 x 3 = 24 minutes
They will ring together again at 12:24 PM.
8.2 Circular Track Problems (LCM Problem)
When two or more people start running simultaneously from the same point on a circular track, they meet at the starting point again after a time equal to the LCM of their individual times to complete one round.
Worked Example:
A and B start running around a circular track from the same point. A completes one round in 12 minutes and B in 18 minutes. After how many minutes will they first meet at the starting point?
LCM(12, 18):
12 = 2^2 x 3
18 = 2 x 3^2
LCM = 2^2 x 3^2 = 4 x 9 = 36 minutes
They first meet at the starting point after 36 minutes.
8.3 Tiling / Cutting Problems (HCF Problem)
To cut a surface into the largest possible identical square tiles, use the HCF of the dimensions.
Worked Example:
A floor of dimensions 24m x 36m is to be paved with square tiles of the largest possible size. Find the tile size and number of tiles needed.
Side of largest square tile = HCF(24, 36) = 12 m
Number of tiles = (Area of floor) / (Area of one tile)
= (24 x 36) / (12 x 12)
= 864 / 144
= 6 tiles
8.4 Maximum Grouping / Distribution (HCF Problem)
To divide items into the largest possible equal groups with nothing left over, use the HCF.
Worked Example:
There are 48 apples, 60 oranges, and 84 bananas. What is the maximum number of baskets that can be made such that each basket has the same number of each fruit and no fruit is left over?
Maximum baskets = HCF(48, 60, 84)
48 = 2^4 x 3
60 = 2^2 x 3 x 5
84 = 2^2 x 3 x 7
HCF = 2^2 x 3 = 12
Each basket: 48/12 = 4 apples, 60/12 = 5 oranges, 84/12 = 7 bananas.
8.5 Scheduling / Recurring Events (LCM Problem)
When events repeat at different intervals, they coincide again after the LCM of the intervals.
Worked Example:
Bus A departs every 15 minutes, Bus B departs every 20 minutes, and Bus C departs every 25 minutes. If all three depart together at 8:00 AM, when will they next depart together?
LCM(15, 20, 25):
15 = 3 x 5
20 = 2^2 x 5
25 = 5^2
LCM = 2^2 x 3 x 5^2 = 4 x 3 x 25 = 300 minutes = 5 hours
They next depart together at 1:00 PM.
8.6 Finding the Largest Number That Divides Given Numbers with Same Remainder
Type 1: Remainder is given.
Find the largest number that divides 65, 81, and 145 leaving a remainder of 5 in each case.
The number divides (65 - 5), (81 - 5), and (145 - 5), i.e., 60, 76, 140.
Required number = HCF(60, 76, 140)
60 = 2^2 x 3 x 5
76 = 2^2 x 19
140 = 2^2 x 5 x 7
HCF = 2^2 = 4
Type 2: Remainder is NOT given (but is the same for all).
Find the largest number that divides 59, 97, and 173 leaving the same remainder in each case.
Take pairwise differences:
97 - 59 = 38
173 - 97 = 76
173 - 59 = 114
Required number = HCF(38, 76, 114)
38 = 2 x 19
76 = 2^2 x 19
114 = 2 x 3 x 19
HCF = 2 x 19 = 38
Verification: 59 / 38 = 1 remainder 21; 97 / 38 = 2 remainder 21; 173 / 38 = 4 remainder 21. Same remainder (21). Correct.
9. Finding the Smallest/Largest Number Divisible by Given Numbers
9.1 Smallest Number Exactly Divisible by All Given Numbers
Answer = LCM of the given numbers
9.2 Smallest Number Which When Divided Leaves Given Remainders
Case 1: Same remainder r for all divisors.
Answer = LCM of divisors + r
Worked Example:
Find the smallest number which when divided by 6, 9, and 15 leaves a remainder of 2 in each case.
LCM(6, 9, 15) = 90
Answer = 90 + 2 = 92
Verification: 92/6 = 15 R 2; 92/9 = 10 R 2; 92/15 = 6 R 2. Correct.
Case 2: Different remainders, but (divisor - remainder) is the same for all.
If d1 - r1 = d2 - r2 = d3 - r3 = k, then:
Answer = LCM(d1, d2, d3) - k
Worked Example:
Find the smallest number which when divided by 5, 7, and 9 leaves remainders 3, 5, and 7 respectively.
Check: 5 - 3 = 2, 7 - 5 = 2, 9 - 7 = 2. All give k = 2.
LCM(5, 7, 9) = 315
Answer = 315 - 2 = 313
Verification: 313/5 = 62 R 3; 313/7 = 44 R 5; 313/9 = 34 R 7. Correct.
9.3 Largest Number Below a Limit Divisible by All Given Numbers
Find LCM, then find the largest multiple of LCM that does not exceed the limit.
Answer = (Limit / LCM) (take floor) x LCM
Worked Example:
Find the largest number less than 1000 that is divisible by 8, 12, and 15.
LCM(8, 12, 15) = 120
Floor(1000 / 120) = Floor(8.33) = 8
Answer = 8 x 120 = 960
10. Summary of All Formulas
1. HCF (Prime Factorization) = Product of LOWEST powers of COMMON primes
2. LCM (Prime Factorization) = Product of HIGHEST powers of ALL primes
3. HCF x LCM = a x b (for exactly two numbers a and b)
4. LCM(a, b) = (a x b) / HCF(a, b)
5. HCF of fractions = HCF of numerators / LCM of denominators
6. LCM of fractions = LCM of numerators / HCF of denominators
7. HCF always divides LCM
8. HCF(a, b) <= min(a, b)
9. LCM(a, b) >= max(a, b)
10. If HCF(a, b) = 1, then LCM(a, b) = a x b
11. If a divides b, then HCF(a, b) = a and LCM(a, b) = b
12. If HCF(a, b) = h, then a = hx, b = hy where HCF(x, y) = 1
13. Smallest number divisible by all = LCM
14. Remainder r for all divisors --> Answer = LCM + r
15. (Divisor - Remainder) = k for all --> Answer = LCM - k
16. Largest divisor leaving same
unknown remainder = HCF of pairwise differences