HCF and LCM for CDS

HCF and LCM questions in CDS rarely ask you to find the HCF of two numbers and stop. They wrap the idea in a story: bells that ring together, tiles that must fit a floor exactly, a number that leaves a given remainder. The arithmetic is easy. The skill is recognising which tool the story needs, and adjusting for remainders before you use it.

This guide builds that skill: the two methods, the product rule, a decision table for word problems, and the four remainder patterns that UPSC keeps returning to.

The two ideas

• HCF (highest common factor): the largest number that divides every given number exactly.
• LCM (lowest common multiple): the smallest number that every given number divides exactly.

Method 1: prime factorisation

Write each number as a product of primes.

• HCF: take each prime that appears in all the numbers, with its lowest power.
• LCM: take every prime that appears in any number, with its highest power.

For 36 = 2² × 3² and 84 = 2² × 3 × 7: HCF = 2² × 3 = 12, and LCM = 2² × 3² × 7 = 252.

Why lowest and highest? A common factor cannot use more of a prime than the number with the fewest of it. A common multiple must contain at least as much of each prime as the number with the most of it.

Method 2: repeated division (Euclid's method)

For large numbers, divide the larger by the smaller, then divide the divisor by the remainder, and repeat until the remainder is 0. The last divisor is the HCF.

For 1,651 and 2,032: 2,032 = 1 × 1,651 + 381; 1,651 = 4 × 381 + 127; 381 = 3 × 127 + 0. The HCF is 127. This works because any number that divides two numbers also divides their difference, so the HCF never changes as you go.

The product rule

For two numbers only:

HCF × LCM = product of the two numbers

It follows from the prime method: for each prime, the lower power goes into the HCF and the higher into the LCM, so between them they use every prime exactly as often as the two numbers do.

Two useful consequences:

• The HCF always divides the LCM. If an option gives an HCF that does not divide the LCM, it is wrong.
• If two numbers have HCF h, they can be written as h × a and h × b, where a and b are co-prime. Many questions become easy in this form.

Which one does the question want?

HCF and LCM of fractions

• HCF of fractions = HCF of the numerators ÷ LCM of the denominators.
• LCM of fractions = LCM of the numerators ÷ HCF of the denominators.

Reduce each fraction to lowest terms first. For 2/3, 4/9 and 5/6: HCF = HCF(2, 4, 5) ÷ LCM(3, 9, 6) = 1/18, and LCM = LCM(2, 4, 5) ÷ HCF(3, 9, 6) = 20/3.

Worked questions

Question 1: Find the HCF and LCM of 72, 108 and 180.

• 72 = 2³ × 3², 108 = 2² × 3³, 180 = 2² × 3² × 5.
• HCF = 2² × 3² = 36.
• LCM = 2³ × 3³ × 5 = 1,080.

Question 2: Find the greatest number that divides 1,657 and 2,037 leaving remainders 6 and 5 respectively.

• Remove the remainders: 1,657 − 6 = 1,651 and 2,037 − 5 = 2,032.
• By Euclid's method above, HCF(1,651, 2,032) = 127.
• Check: 1,657 = 13 × 127 + 6, and 2,037 = 16 × 127 + 5.

Question 3: Find the least number which, when divided by 12, 15, 20 and 54, leaves remainder 8 in each case.

• 12 = 2² × 3, 15 = 3 × 5, 20 = 2² × 5, 54 = 2 × 3³.
• LCM = 2² × 3³ × 5 = 540.
• Add the common remainder: 540 + 8 = 548.

Question 4: Find the least number which leaves remainders 3, 4 and 5 when divided by 4, 5 and 6 respectively.

• In each case, divisor − remainder = 1. So the number is 1 short of a common multiple.
• LCM(4, 5, 6) = 60, so the number is 60 − 1 = 59.

Question 5: A room is 6.24 m long and 4.32 m wide. It is to be paved with identical square tiles, with no cutting. Find the least number of tiles.

• Least number of tiles means the largest tile, which is the HCF of the sides in centimetres.
• 624 = 2⁴ × 3 × 13 and 432 = 2⁴ × 3³, so HCF = 2⁴ × 3 = 48 cm.
• Tiles = (624 ÷ 48) × (432 ÷ 48) = 13 × 9 = 117.

Question 6: Four bells toll at intervals of 6, 8, 12 and 18 seconds. They toll together at the start. How many times do they toll together in 30 minutes, not counting the start?

• LCM(6, 8, 12, 18) = 2³ × 3² = 72 seconds.
• 30 minutes = 1,800 seconds, and 1,800 ÷ 72 = 25 times after the start (26 if the start is counted).

Practice set

1. Find the HCF and LCM of 48 and 72.
2. Two numbers have HCF 6 and LCM 180. One number is 30. Find the other.
3. Find the smallest number divisible by 8, 12 and 18.
4. Two lights flash every 20 and 30 seconds. They flash together now. When will they next flash together?
5. Find the greatest number that divides 43, 91 and 183 leaving the same remainder in each case.
6. Find the least four-digit number divisible by 12, 15 and 20.
7. Find the least number which leaves remainder 4 when divided by 6, 9, 15 and 18, and is exactly divisible by 7.
8. The HCF of two numbers is 11 and their sum is 132. How many such pairs of numbers are there?

Answers

1. HCF 24, LCM 144. 48 = 2⁴ × 3 and 72 = 2³ × 3², so HCF = 2³ × 3 and LCM = 2⁴ × 3².
2. 36. 6 × 180 = 1,080, and 1,080 ÷ 30 = 36. Check: HCF(30, 36) = 6 and LCM = 180.
3. 72. 8 = 2³, 12 = 2² × 3, 18 = 2 × 3², so LCM = 2³ × 3².
4. After 60 seconds. LCM(20, 30) = 60.
5. 4. The differences are 48, 92 and 140, and their HCF is 4. Each number leaves remainder 3.
6. 1,020. LCM = 60. 1,000 ÷ 60 is between 16 and 17, so take 17 × 60 = 1,020.
7. 364. LCM(6, 9, 15, 18) = 90, so the number is 90k + 4. Try k = 1, 2, 3, 4: 94, 184, 274, 364. Only 364 = 7 × 52 is divisible by 7.
8. 2. Write the numbers as 11a and 11b with a and b co-prime, so a + b = 12. The co-prime pairs are (1, 11) and (5, 7), giving 11 and 121, and 55 and 77.

What to do next

• Add the decision table and the fraction rule to your formula sheet
• Redo questions 2 to 4 without looking, and say which row of the table each one uses
• Solve the HCF and LCM questions from the last five CDS papers, timed
• Revise prime factorisation in the number system guide if any step felt slow
• Move on to fractions, decimals and roots