Episode 8 — Aptitude and Reasoning / 8.7 — HCF and LCM
8.7.c Solved Examples
Attempt each problem on your own before reading the solution. Problems are arranged by difficulty.
Basic Level
Problem 1: Find HCF by Prime Factorization
Find the HCF of 84 and 126.
Solution:
84 = 2^2 x 3 x 7
126 = 2 x 3^2 x 7
Common prime factors: 2, 3, 7
Lowest powers: 2^1, 3^1, 7^1
HCF = 2 x 3 x 7 = 42
Answer: 42
Problem 2: Find LCM by Prime Factorization
Find the LCM of 16, 24, and 36.
Solution:
16 = 2^4
24 = 2^3 x 3
36 = 2^2 x 3^2
All prime factors: 2, 3
Highest powers: 2^4, 3^2
LCM = 2^4 x 3^2 = 16 x 9 = 144
Answer: 144
Problem 3: Find HCF Using Long Division
Find the HCF of 867 and 255.
Solution:
867 = 255 x 3 + 102
255 = 102 x 2 + 51
102 = 51 x 2 + 0
HCF = 51
Verification: 867 / 51 = 17, 255 / 51 = 5. Both exact.
Answer: 51
Problem 4: LCM Using Common Division
Find the LCM of 10, 15, 20, and 25.
Solution:
2 | 10 15 20 25
2 | 5 15 10 25
3 | 5 15 5 25
5 | 5 5 5 25
5 | 1 1 1 5
| 1 1 1 1
LCM = 2 x 2 x 3 x 5 x 5 = 300
Answer: 300
Problem 5: Product Rule
The HCF of two numbers is 8 and their LCM is 480. If one number is 32, find the other.
Solution:
HCF x LCM = a x b
8 x 480 = 32 x b
3840 = 32b
b = 3840 / 32 = 120
Verification: HCF(32, 120) = 8, LCM(32, 120) = (32 x 120)/8 = 480. Correct.
Answer: 120
Problem 6: HCF and LCM of Fractions
Find the HCF and LCM of 3/5, 6/11, and 9/20.
Solution:
Numerators: 3, 6, 9
HCF(3, 6, 9) = 3
LCM(3, 6, 9) = 18
Denominators: 5, 11, 20
HCF(5, 11, 20) = 1
LCM(5, 11, 20) = 220
HCF of fractions = HCF of numerators / LCM of denominators = 3/220
LCM of fractions = LCM of numerators / HCF of denominators = 18/1 = 18
Answer: HCF = 3/220, LCM = 18
Problem 7: Co-prime Check
Are 91 and 153 co-prime?
Solution:
HCF(91, 153):
153 = 91 x 1 + 62
91 = 62 x 1 + 29
62 = 29 x 2 + 4
29 = 4 x 7 + 1
4 = 1 x 4 + 0
HCF = 1
Since HCF = 1, the numbers are co-prime.
Answer: Yes, 91 and 153 are co-prime.
Medium Level
Problem 8: Bells Ringing Together
Four bells ring at intervals of 4, 6, 8, and 14 seconds. If they all ring together at a certain instant, after how many seconds will they ring together again?
Solution:
LCM(4, 6, 8, 14):
4 = 2^2
6 = 2 x 3
8 = 2^3
14 = 2 x 7
LCM = 2^3 x 3 x 7 = 8 x 3 x 7 = 168 seconds
168 seconds = 2 minutes 48 seconds
Answer: 168 seconds (2 minutes 48 seconds)
Problem 9: Circular Track
Three runners A, B, and C run around a circular track starting from the same point at the same time. They complete one round in 10, 15, and 20 minutes respectively. After how many minutes will all three meet at the starting point for the first time?
Solution:
LCM(10, 15, 20):
10 = 2 x 5
15 = 3 x 5
20 = 2^2 x 5
LCM = 2^2 x 3 x 5 = 60 minutes
Answer: 60 minutes (1 hour)
Problem 10: Tiling a Room
A room is 15m 17cm long and 9m 02cm wide. Find the largest square tile that can exactly pave the floor. Also find the number of tiles needed.
Solution:
Length = 1517 cm, Width = 902 cm
Side of largest tile = HCF(1517, 902)
1517 = 902 x 1 + 615
902 = 615 x 1 + 287
615 = 287 x 2 + 41
287 = 41 x 7 + 0
HCF = 41 cm
Number of tiles = (1517 / 41) x (902 / 41)
= 37 x 22
= 814
Answer: Tile side = 41 cm, Number of tiles = 814
Problem 11: Largest Divisor with Same Remainder
Find the largest number that divides 245, 1029, and 1433 leaving the same remainder in each case.
Solution:
Take pairwise differences:
1029 - 245 = 784
1433 - 1029 = 404
1433 - 245 = 1188
HCF(784, 404):
784 = 404 x 1 + 380
404 = 380 x 1 + 24
380 = 24 x 15 + 20
24 = 20 x 1 + 4
20 = 4 x 5 + 0
HCF(784, 404) = 4
HCF(4, 1188):
1188 = 4 x 297 + 0
HCF = 4
Answer = 4
Verification: 245/4 = 61 R 1; 1029/4 = 257 R 1; 1433/4 = 358 R 1. Same remainder. Correct.
Answer: 4
Problem 12: Smallest Number with Given Remainders (Same Remainder)
Find the smallest number which when divided by 12, 16, and 24 leaves a remainder of 7 in each case.
Solution:
LCM(12, 16, 24):
12 = 2^2 x 3
16 = 2^4
24 = 2^3 x 3
LCM = 2^4 x 3 = 48
Required number = LCM + remainder = 48 + 7 = 55
Verification: 55/12 = 4 R 7; 55/16 = 3 R 7; 55/24 = 2 R 7. Correct.
Answer: 55
Problem 13: Smallest Number with Remainders (Deficit Pattern)
Find the smallest number which when divided by 8, 12, and 15 leaves remainders 3, 7, and 10 respectively.
Solution:
Check for deficit pattern:
8 - 3 = 5
12 - 7 = 5
15 - 10 = 5
Deficit k = 5 (same for all), so this is the deficit pattern.
LCM(8, 12, 15):
8 = 2^3
12 = 2^2 x 3
15 = 3 x 5
LCM = 2^3 x 3 x 5 = 120
Required number = LCM - k = 120 - 5 = 115
Verification: 115/8 = 14 R 3; 115/12 = 9 R 7; 115/15 = 7 R 10. Correct.
Answer: 115
Problem 14: Finding Number Pairs
Find all pairs of numbers whose HCF is 3 and LCM is 180.
Solution:
h = 3, L = 180
Check: 180 / 3 = 60 (integer, so valid)
Let numbers be 3x and 3y, where HCF(x, y) = 1 and x * y = 60.
Factor pairs of 60 that are co-prime:
1 x 60: HCF(1, 60) = 1 --> (3, 180)
3 x 20: HCF(3, 20) = 1 --> (9, 60)
4 x 15: HCF(4, 15) = 1 --> (12, 45)
5 x 12: HCF(5, 12) = 1 --> (15, 36)
Rejected pairs (not co-prime):
2 x 30: HCF(2, 30) = 2 --> reject
6 x 10: HCF(6, 10) = 2 --> reject
Answer: (3, 180), (9, 60), (12, 45), (15, 36)
Problem 15: Distribution Problem
A shopkeeper has 120 pens, 168 pencils, and 192 erasers. He wants to pack them in identical packets such that each packet has the same number of pens, the same number of pencils, and the same number of erasers, with nothing left over. What is the maximum number of packets?
Solution:
Maximum packets = HCF(120, 168, 192)
120 = 2^3 x 3 x 5
168 = 2^3 x 3 x 7
192 = 2^6 x 3
HCF = 2^3 x 3 = 24
Each packet: 120/24 = 5 pens, 168/24 = 7 pencils, 192/24 = 8 erasers.
Answer: 24 packets
Problem 16: Scheduling Problem
A traffic light turns red every 56 seconds, another every 84 seconds, and a third every 140 seconds. If all three turn red simultaneously at 8:00:00 AM, when will they next turn red together?
Solution:
LCM(56, 84, 140):
56 = 2^3 x 7
84 = 2^2 x 3 x 7
140 = 2^2 x 5 x 7
LCM = 2^3 x 3 x 5 x 7 = 8 x 3 x 5 x 7 = 840 seconds
840 seconds = 14 minutes
Answer: 8:14:00 AM (after 14 minutes)
Problem 17: Rope Cutting
Three ropes of lengths 36m, 48m, and 84m are to be cut into pieces of equal length. Find the maximum possible length of each piece.
Solution:
Maximum length = HCF(36, 48, 84)
36 = 2^2 x 3^2
48 = 2^4 x 3
84 = 2^2 x 3 x 7
HCF = 2^2 x 3 = 12 m
Number of pieces = 36/12 + 48/12 + 84/12 = 3 + 4 + 7 = 14
Answer: 12 m (14 pieces total)
Advanced Level
Problem 18: Finding Numbers from HCF, LCM, and Sum
The HCF of two numbers is 12 and their LCM is 360. If the sum of the two numbers is 108, find the two numbers.
Solution:
Let the numbers be 12x and 12y, where HCF(x, y) = 1.
LCM = 12 x y = 360 --> x * y = 30
Sum: 12x + 12y = 108 --> x + y = 9
So we need: x + y = 9 and x * y = 30 and HCF(x, y) = 1.
These are roots of: t^2 - 9t + 30 = 0
t = [9 +/- sqrt(81 - 120)] / 2
t = [9 +/- sqrt(-39)] / 2
Discriminant is negative! No real solution exists.
Wait -- let us recheck. Actually, let's look for integer pairs with sum 9 and product 30:
Pairs summing to 9: (1,8), (2,7), (3,6), (4,5)
Products: 8, 14, 18, 20
None gives product 30. So no valid pair exists with these constraints.
Hmm, let us re-examine. The problem as stated has no solution. This is actually a common exam trap -- not all given constraints are always compatible.
But let us modify: If the sum is 132 instead:
12x + 12y = 132 --> x + y = 11
x * y = 30
Co-prime pairs with product 30 and sum 11:
(5, 6): product = 30, sum = 11, HCF(5,6) = 1. Valid!
Numbers: 12 x 5 = 60 and 12 x 6 = 72
Verification: HCF(60, 72) = 12. LCM(60, 72) = (60 x 72)/12 = 360. Sum = 132. Correct.
Answer: 60 and 72
Key takeaway: Always verify that the given constraints (HCF, LCM, sum/difference) are mutually consistent.
Problem 19: Largest Number Below a Limit with Remainder Conditions
Find the largest 4-digit number which when divided by 4, 7, and 13 leaves a remainder of 3 in each case.
Solution:
LCM(4, 7, 13) = 4 x 7 x 13 = 364 (all co-prime)
Numbers of the form: 364k + 3
Largest 4-digit number = 9999
364k + 3 <= 9999
364k <= 9996
k <= 27.46
k = 27: 364 x 27 + 3 = 9828 + 3 = 9831
Verification: 9831/4 = 2457 R 3; 9831/7 = 1404 R 3; 9831/13 = 756 R 3. Correct.
Answer: 9831
Problem 20: Number of Pairs with Given HCF and LCM
How many pairs of numbers have HCF = 6 and LCM = 210?
Solution:
Check: 210 / 6 = 35 (integer, valid)
Let the numbers be 6x and 6y, where HCF(x, y) = 1 and x * y = 35.
Factor pairs of 35:
1 x 35: HCF(1, 35) = 1 --> valid: (6, 210)
5 x 7: HCF(5, 7) = 1 --> valid: (30, 42)
Answer: 2 pairs -- (6, 210) and (30, 42)
Problem 21: Multiple Intervals with Different Start Times
Two alarms go off at intervals of 20 minutes and 30 minutes. If the first alarm last went off at 9:15 AM and the second at 9:25 AM, when will they go off together for the first time?
Solution:
LCM(20, 30) = 60 minutes
First alarm times: 9:15, 9:35, 9:55, 10:15, 10:35, 10:55, 11:15, ...
Second alarm times: 9:25, 9:55, 10:25, 10:55, 11:25, ...
We need the earliest time common to both sequences.
From the lists: 9:55 appears in both!
First alarm: 9:15 + 2(20) = 9:15 + 40 = 9:55
Second alarm: 9:25 + 1(30) = 9:25 + 30 = 9:55
Alternative approach: First alarm at times 9:15 + 20m; Second alarm at 9:25 + 30n. Solve: 15 + 20m = 25 + 30n --> 20m - 30n = 10 --> 2m - 3n = 1. Smallest non-negative solution: m=2, n=1. Time = 9:15 + 40 = 9:55.
Answer: 9:55 AM
Problem 22: Finding HCF When Given Remainders
When 2011 and 2623 are divided by a 3-digit number N, the remainders are 11 and 23 respectively. Find N.
Solution:
2011 = N x q1 + 11 --> N divides (2011 - 11) = 2000
2623 = N x q2 + 23 --> N divides (2623 - 23) = 2600
N is a common factor of 2000 and 2600.
N is a 3-digit number.
HCF(2000, 2600):
2000 = 2^4 x 5^3
2600 = 2^3 x 5^2 x 13
HCF = 2^3 x 5^2 = 200
Factors of 200 that are 3-digit: 200 itself.
But let us also check other common factors of 2000 and 2600:
Common factors must divide HCF(2000, 2600) = 200.
Factors of 200: 1, 2, 4, 5, 8, 10, 20, 25, 40, 50, 100, 200
3-digit factors: 100, 200
But wait: N must be greater than the remainder in each case.
N > 11 and N > 23, so N >= 24. Both 100 and 200 qualify.
However, we also need N to be a factor of BOTH 2000 and 2600.
100 divides 2000? 2000/100 = 20. Yes.
100 divides 2600? 2600/100 = 26. Yes.
200 divides 2000? 2000/200 = 10. Yes.
200 divides 2600? 2600/200 = 13. Yes.
Both are valid. But the problem says "a 3-digit number N" (singular), suggesting a unique answer. If the question asks for the largest such number:
N = 200.
Answer: N = 200 (largest 3-digit number satisfying the condition)
Problem 23: Day-Off Scheduling
Three workers have days off in cycles of 3, 4, and 5 days respectively. If they all have a day off on January 1, on how many days in January will all three have a day off together?
Solution:
LCM(3, 4, 5) = 60
They share a day off every 60 days.
January 1 is a shared day off. The next would be after 60 days (March 2).
So in January, they share a day off only on January 1.
But wait -- let us be more careful about what "cycle" means. If a worker has a day off every 3 days starting from Jan 1:
Worker A (every 3 days): Jan 1, Jan 4, Jan 7, Jan 10, ...
Worker B (every 4 days): Jan 1, Jan 5, Jan 9, Jan 13, ...
Worker C (every 5 days): Jan 1, Jan 6, Jan 11, Jan 16, ...
Common days = every LCM(3,4,5) = 60 days after Jan 1.
Next: Jan 1 + 60 days = March 2.
In January: only January 1.
Answer: 1 day (January 1 only)
Problem 24: Maximum Containers Problem
A milkman has 75 litres of milk and 45 litres of water. He wants to fill them in containers of equal capacity such that each container has only milk or only water (not a mix), and no liquid is left over. What is the maximum capacity of each container, and how many containers of each type?
Solution:
Maximum capacity = HCF(75, 45)
75 = 3 x 5^2
45 = 3^2 x 5
HCF = 3 x 5 = 15 litres
Milk containers: 75 / 15 = 5
Water containers: 45 / 15 = 3
Total containers: 5 + 3 = 8
Answer: 15 litres per container; 5 milk containers and 3 water containers
Problem 25: LCM-Based Problem with a Twist
The LCM of two numbers is 12 times their HCF. The sum of HCF and LCM is 403. If one number is 93, find the other.
Solution:
Let HCF = h, LCM = L.
L = 12h ...(1)
h + L = 403 ...(2)
From (1) and (2): h + 12h = 403 --> 13h = 403 --> h = 31
L = 12 x 31 = 372
One number = 93.
Other number = (h x L) / 93 = (31 x 372) / 93 = 11532 / 93 = 124
Verification: HCF(93, 124) = 31. LCM(93, 124) = (93 x 124)/31 = 372. L/h = 372/31 = 12. h + L = 31 + 372 = 403. All correct.
Answer: 124
Problem 26: Circular Track -- First Meeting Anywhere
Two runners A and B start from the same point on a circular track of length 600m. A runs at 5 m/s and B runs at 3 m/s in the same direction. After how long will they meet for the first time?
Solution:
This is NOT a straightforward LCM problem. When running in the same direction,
they meet when the faster runner gains exactly one full lap over the slower.
Relative speed = 5 - 3 = 2 m/s
Distance to gain = 600 m (one full lap)
Time = 600 / 2 = 300 seconds = 5 minutes
Note: If running in opposite directions, relative speed = 5 + 3 = 8 m/s, time = 600/8 = 75 seconds.
For meeting at the STARTING point (different question):
Time for A to complete one round = 600/5 = 120 s
Time for B to complete one round = 600/3 = 200 s
They meet at starting point after LCM(120, 200) = 600 seconds = 10 minutes
Answer: 300 seconds (first meeting anywhere); 600 seconds (first meeting at starting point)
Problem 27: Three-Number Advanced Problem
Find three numbers in the ratio 1:2:3 whose LCM is 120.
Solution:
Let the numbers be k, 2k, 3k.
LCM(k, 2k, 3k) = k x LCM(1, 2, 3) = k x 6
k x 6 = 120
k = 20
Numbers: 20, 40, 60
Verification: LCM(20, 40, 60) = ?
20 = 2^2 x 5
40 = 2^3 x 5
60 = 2^2 x 3 x 5
LCM = 2^3 x 3 x 5 = 120. Correct.
Answer: 20, 40, 60
Problem 28: Product of Three Numbers Given HCF and LCM Data
The HCF of two numbers is 11 and their LCM is 385. If one number lies between 60 and 80, find the number.
Solution:
Let the numbers be 11x and 11y, where HCF(x, y) = 1.
LCM = 11 x y = 385 --> x * y = 35
Co-prime pairs with product 35:
(1, 35): HCF(1, 35) = 1 --> Numbers: 11, 385
(5, 7): HCF(5, 7) = 1 --> Numbers: 55, 77
The number between 60 and 80 is 77.
Answer: 77
Summary Table
| # | Type | Difficulty | Key Concept Used |
|---|---|---|---|
| 1 | Find HCF | Basic | Prime factorization |
| 2 | Find LCM | Basic | Prime factorization |
| 3 | Find HCF | Basic | Long division |
| 4 | Find LCM | Basic | Common division |
| 5 | Product rule | Basic | HCF x LCM = product |
| 6 | Fractions | Basic | HCF/LCM of fractions |
| 7 | Co-prime check | Basic | Euclidean algorithm |
| 8 | Bells | Medium | LCM |
| 9 | Circular track | Medium | LCM |
| 10 | Tiling | Medium | HCF |
| 11 | Same remainder (unknown) | Medium | HCF of differences |
| 12 | Remainder (same) | Medium | LCM + r |
| 13 | Remainder (deficit) | Medium | LCM - k |
| 14 | Find pairs | Medium | Co-prime factor pairs |
| 15 | Distribution | Medium | HCF |
| 16 | Scheduling | Medium | LCM |
| 17 | Rope cutting | Medium | HCF |
| 18 | HCF, LCM, Sum | Advanced | Quadratic / constraints |
| 19 | Largest 4-digit | Advanced | LCM + remainder with limit |
| 20 | Count pairs | Advanced | Co-prime enumeration |
| 21 | Different start times | Advanced | LCM + sequence matching |
| 22 | Given remainders | Advanced | Common factors |
| 23 | Day-off scheduling | Advanced | LCM |
| 24 | Container problem | Advanced | HCF |
| 25 | LCM = k x HCF | Advanced | Algebraic + product rule |
| 26 | Circular track (anywhere) | Advanced | Relative speed vs LCM |
| 27 | Ratio + LCM | Advanced | Ratio with LCM |
| 28 | Range constraint | Advanced | Co-prime pairs + range |
Next: 8.7 Practice MCQs