RPSC RAS / RTS course‹› 0:00 studied

RPSC RAS / RTS · Module 63 · Mains depth · 21 min

Divisibility, factors, HCF and LCM

What RPSC RAS / RTS asks from this chapter

Syllabus lines this chapter covers:

  • General Knowledge and General Science · Mental ability: number and letter series, coding-decoding, blood relations, direction sense, Venn diagrams, ranking and seating arrangement, shapes and their sub-sections.
  • General Knowledge and General Science · Basic numeracy: ratio, proportion and partnership, profit and loss, percentage, simple and compound interest, perimeter and area, data analysis, mean, median and mode, permutation and combination, simple probability.

RPSC RAS / RTS questions from this module are being sorted into our bank.

Read at full depth: basics, the standard layer and the Mains analysis.

Start from zero: sharing sweets and waiting for buses

Your mother has made 12 laddoos and wants to share them equally, with none left over. She can give them to 1, 2, 3, 4, 6 or 12 children, but not to 5 or 7. The numbers that share 12 exactly are its factors.

Twelve laddoos, shared fairly

Now think of the bus stand. One bus leaves every 12 minutes and another every 18 minutes, and both left together at 9:00. They will leave together again only at a time that is a multiple of both 12 and 18, and the first such time is 36 minutes later, at 9:36.

These two everyday questions carry the whole chapter. "What divides evenly?" leads to factors and the HCF, the highest common factor. "When do two cycles meet again?" leads to multiples and the LCM, the least common multiple.

The papers ask these ideas in many disguises, such as tiles, bells, packets and remainders. If you learn why each rule works, the disguise stops mattering. So we build the tools first and then learn to spot which one a question needs.

Factors, multiples and prime factorisation

Factors and multiples. A factor of a number divides it with no remainder, so the factors of 18 are 1, 2, 3, 6, 9 and 18. A multiple of a number is that number times 1, 2, 3 and so on, so the multiples of 18 are 18, 36, 54 and so on. A number has only a few factors but endlessly many multiples.

A factor tree for 360

Breaking a number into primes. Keep splitting a number until only primes are left, as in a factor tree. For 360, we get 360 = 2 × 180 = 2 × 2 × 90, and going on, 360 = 2³ × 3² × 5. Whichever way you split, you always reach the same primes with the same powers, and this is why prime factorisation is so reliable.

Counting factors without listing them. Every factor of 360 is made by choosing a power of 2 from 2⁰ to 2³, a power of 3 from 3⁰ to 3², and a power of 5 from 5⁰ to 5¹. That gives 4 choices, 3 choices and 2 choices, so 360 has 4 × 3 × 2 = 24 factors. In general, if N = pᵃ × qᵇ × rᶜ, the number of factors is (a + 1)(b + 1)(c + 1).

Why the "+1" is there. The "+1" counts the choice of not using that prime at all, which is the power 0. Leaving it out is the most common slip in this question type. Check with a small number: 12 = 2² × 3 has (2 + 1)(1 + 1) = 6 factors, and indeed they are 1, 2, 3, 4, 6 and 12.

Why it matters: prime factorisation is the master key of this chapter. Once a number is written as primes, its factors, its HCF and LCM with other numbers, and even whether it is a perfect square, can all be read off directly.

Divisibility tests, and why they work

Tests from the last digits. A number is divisible by 2 if its last digit is even, by 5 if it ends in 0 or 5, and by 10 if it ends in 0. It is divisible by 4 if its last two digits form a multiple of 4, and by 8 if its last three digits form a multiple of 8. These work because 100 is a multiple of 4 and 1,000 is a multiple of 8, so the earlier digits never change the answer.

Why the digit-sum test works for 9

Tests from the digit sum. A number is divisible by 3 if the sum of its digits is divisible by 3, and by 9 if the digit sum is divisible by 9. The reason is that 10, 100 and 1,000 are each one more than a multiple of 9 (9, 99, 999). So 4,356 = 4 × 999 + 3 × 99 + 5 × 9 + (4 + 3 + 5 + 6), and only the bracket decides the remainder.

The test for 11. Add the digits in the odd places from the right, add the digits in the even places, and subtract. If the difference is 0 or a multiple of 11, the number is divisible by 11. For 95,876, the sums are 6 + 8 + 9 = 23 and 7 + 5 = 12, and 23 − 12 = 11, so it passes, and indeed 95,876 = 11 × 8,716.

Composite divisors. To test for 6, test for 2 and 3, because 2 and 3 share no factor. To test for 12, test for 3 and 4, not for 2 and 6, because 2 and 6 overlap. For example, 18 passes the tests for 2 and 6, yet 18 is not divisible by 12.

Why it matters: these tests let you decide in seconds whether a number divides another, which is the first step in simplifying fractions, finding a missing digit, or checking an answer option.

The HCF: the biggest number that divides them all

Meaning. The HCF (highest common factor), also called the GCD, is the largest number that divides each of the given numbers exactly. The HCF of 144 and 180 is the largest number that divides both, and it turns out to be 36.

Euclid's method as cutting squares from a rectangle

Method 1: prime factors. Write 144 = 2⁴ × 3² and 180 = 2² × 3² × 5. Take only the primes common to both, each with its lowest power, so the HCF is 2² × 3² = 36. The lowest power is used because any higher power would fail to divide the number that has fewer of that prime.

Method 2: Euclid's division. Divide the larger number by the smaller and keep the remainder: 180 = 1 × 144 + 36. Now divide 144 by 36: 144 = 4 × 36 + 0. When the remainder becomes 0, the last divisor, 36, is the HCF.

Why Euclid's method works. Any number that divides both 180 and 144 also divides their difference, 36, and any number that divides 144 and 36 also divides 180. So the pair (180, 144) and the pair (144, 36) have exactly the same common factors, and therefore the same HCF. Each step makes the numbers smaller without changing the answer, which is why the method is so fast for big numbers.

Why it matters: the HCF answers every "largest possible equal size" question, such as the biggest tile, the longest measuring rod or the largest equal group.

The LCM: the smallest number they all divide

Meaning. The LCM (least common multiple) is the smallest number that is a multiple of each given number. For 144 and 180 it is 720, because 720 = 5 × 144 = 4 × 180, and no smaller number is a multiple of both.

Lowest powers make the HCF, highest powers make the LCM

Method: highest powers. Take every prime that appears in any of the numbers, each with its highest power. From 144 = 2⁴ × 3² and 180 = 2² × 3² × 5, the LCM is 2⁴ × 3² × 5 = 720. The highest power is needed because the LCM must contain each number completely.

The product rule for two numbers. For any two numbers, HCF × LCM = the product of the numbers. Here 36 × 720 = 25,920 and 144 × 180 = 25,920. The reason is that for each prime, the HCF takes the smaller power and the LCM takes the larger, so together they use exactly the powers of both numbers.

HCF and LCM of fractions. First write each fraction in its lowest terms. Then HCF = HCF of the numerators ÷ LCM of the denominators, and LCM = LCM of the numerators ÷ HCF of the denominators. For ²⁄₃ and ⁴⁄₉, the HCF is ²⁄₉ and the LCM is ⁴⁄₃, and you can check that ⁴⁄₃ is exactly 2 times ²⁄₃ and 3 times ⁴⁄₉.

Why it matters: the LCM answers every "when do they meet again" question, such as buses, bells, traffic lights, duty rosters and machines on different cycles.

HCF or LCM? Reading the word problem

The two-question test. Ask yourself whether the answer must divide the given numbers or must be divided by them. If the answer divides them, as with the largest tile or the longest rod, use the HCF. If the answer is a common multiple, as with "together again" or "the smallest number divisible by", use the LCM.

HCF or LCM? A two-question test

Same remainder, largest divisor. "Find the largest number that divides 43, 91 and 183 leaving the same remainder." If each number leaves the same remainder, their differences leave none. The differences are 48, 92 and 140, and their HCF is 4, so the answer is 4, and indeed each number leaves remainder 3.

Given remainder, smallest number. "Find the smallest number that leaves remainder 5 when divided by 12, 15 and 20." A number divisible by all three is a multiple of their LCM, 60, so add 5 to get 65. If the remainders were 8, 11 and 16, notice that each is 4 short of its divisor, so the answer is 60 − 4 = 56.

Fixed remainder, largest divisor. "Find the largest number that divides 245 and 1,029 leaving remainder 5 in each case." Subtract the remainder first, which gives 240 and 1,024. Their HCF is 16, and this is the answer.

Why it matters: the same two tools solve a dozen question types once you translate the words. Spend your first ten seconds deciding "divides or is divided by", and the arithmetic is usually short.

Where and why this is asked

The officer's version of these problems. A block office sending relief kits wants equal packets with nothing left over, which is an HCF question. A transport officer setting bus timings, a hospital planning nurse shifts, or a police station rotating duties needs to know when cycles line up, which is an LCM question. The exam uses tiles and bells, but the thinking is the same as in real planning work.

Three buses leaving a depot

Where it shows up. Direct questions on factors, divisibility and HCF or LCM appear in every aptitude paper. The ideas also sit underneath fractions, ratios, time and work, clocks and calendars. So a student who is quick with prime factors gains speed across many chapters.

When it goes wrong. Using the LCM where the HCF is needed gives an answer bigger than the numbers you started with, which is impossible for a "largest tile" question. Using the product rule for three numbers gives a wrong value that often appears among the options. These mistakes are predictable, which is exactly why examiners put them in the options.

The habit to build. Write the prime factors first, decide whether the answer divides or is divided by the given numbers, and check the size of your answer. An HCF must be no bigger than the smallest number, and an LCM must be no smaller than the largest.

Exam lens: six question types and how to beat each

These are practice questions written by us, in the styles the papers use. Real past questions from your exam appear in the PYQ panel of this module.

Tiling a floor with the largest square tile

Type 1: counting factors. "How many factors does 360 have?" Write 360 = 2³ × 3² × 5, and the count is (3 + 1)(2 + 1)(1 + 1) = 24. This should take under 40 seconds.

Type 2: the missing digit. "The number 74□8 is divisible by 9. What is the missing digit?" The known digits add to 19, and the next multiple of 9 is 27, so the digit is 8. For 11, use the alternate-sum test in the same way: in 9□876 the sums are 6 + 8 + 9 = 23 and 7 + □, so □ = 5 makes the difference 11.

Type 3: HCF, LCM and one number given. "The HCF of two numbers is 12, their LCM is 360, and one number is 72. Find the other." The other number is 12 × 360 ÷ 72 = 60. Check that 60 and 72 really have HCF 12 and LCM 360 before you mark it.

Type 4: remainders. Use the three patterns: the HCF of differences for the same remainder, LCM + r for a given remainder, and LCM − k when each remainder is k short of its divisor. Always test your answer on one of the numbers.

Type 5: tiles and rods. "A floor is 6 m 24 cm by 4 m 32 cm. Find the largest square tile that fits exactly and the number of tiles." Convert to centimetres, 624 and 432, whose HCF is 48 cm. So you need (624 ÷ 48) × (432 ÷ 48) = 13 × 9 = 117 tiles.

Type 6: cycles meeting. "Three bells ring every 6, 8 and 12 minutes and ring together at 9:00. When do they next ring together?" The LCM is 24 minutes, so the answer is 9:24. If the question asks how many times they ring together in two hours, count 120 ÷ 24 = 5 more times after 9:00.

Time plan. Types 1, 2 and 6 should take under a minute each. Types 3, 4 and 5 can take about a minute and a half, mainly for the check.

Practice set: twelve solved problems

Try each problem first, then read the steps. The problems go from easy to hard.

Practice: remainders on a number line

1. Is 7,452 divisible by 4, by 9 and by 12?

The last two digits, 52, are a multiple of 4, and the digit sum is 18, a multiple of 9. Since it passes 3 and 4, it is also divisible by 12, so the answer is yes to all three.

2. Write 1,260 as a product of primes.

Split it as 1,260 = 2 × 630 = 2 × 2 × 315 = 2² × 3² × 35. So 1,260 = 2² × 3² × 5 × 7.

3. How many factors does 1,260 have?

From 2² × 3² × 5 × 7, the count is 3 × 3 × 2 × 2. So it has 36 factors.

4. Find the HCF of 84 and 126.

Since 84 = 2² × 3 × 7 and 126 = 2 × 3² × 7, take the lowest powers of the common primes. The HCF is 2 × 3 × 7 = 42.

5. Find the LCM of 84 and 126.

Take the highest powers of all primes: 2² × 3² × 7 = 252. Check with the product rule: 42 × 252 = 10,584 = 84 × 126.

6. Use Euclid's method to find the HCF of 1,071 and 462.

First 1,071 = 2 × 462 + 147, then 462 = 3 × 147 + 21, and then 147 = 7 × 21 + 0. So the HCF is 21.

7. Find the HCF and LCM of ³⁄₄, ⁹⁄₁₀ and ⁶⁄₅.

HCF = HCF(3, 9, 6) ÷ LCM(4, 10, 5) = ³⁄₂₀. LCM = LCM(3, 9, 6) ÷ HCF(4, 10, 5) = 18, and the HCF is ³⁄₂₀.

8. The digit □ in 5,□34 makes the number divisible by 3. What is the smallest such digit?

The known digits add to 12, which is already a multiple of 3. So the smallest digit is 0, and the next ones are 3, 6 and 9.

9. Find the largest number that divides 43, 91 and 183 leaving the same remainder.

The differences are 48, 92 and 140, and their HCF is 4. So the answer is 4, with remainder 3 each time.

10. Find the smallest number that leaves remainders 8, 11 and 16 when divided by 12, 15 and 20.

Each remainder is 4 short of its divisor, and the LCM of 12, 15 and 20 is 60. So the answer is 60 − 4 = 56.

11. Two numbers have HCF 12 and LCM 360, and one of them is 72. Find the other.

The other number is 12 × 360 ÷ 72. So it is 60, and HCF(60, 72) = 12 confirms it.

12. A floor is 6 m 24 cm by 4 m 32 cm. How many of the largest square tiles cover it exactly?

The HCF of 624 and 432 is 48, so each tile is 48 cm wide. The floor takes 13 tiles one way and 9 the other, so it needs 117 tiles.

Quick revision

One-page summary box
  • A factor divides a number exactly, and every whole number above 1 breaks into primes in only one way.
  • If N = pᵃ × qᵇ × rᶜ, then N has (a + 1)(b + 1)(c + 1) factors.
  • The tests for 4 and 8 use the last two and last three digits, the tests for 3 and 9 use the digit sum, and the test for 11 uses the alternate-digit difference.
  • For a composite divisor such as 12, test its co-prime parts, 3 and 4.
  • The HCF uses the common primes with their lowest powers, and Euclid's division reaches it quickly.
  • The LCM uses all primes with their highest powers, and for two numbers HCF × LCM equals their product.
  • For fractions, HCF = HCF of numerators ÷ LCM of denominators, and LCM = LCM of numerators ÷ HCF of denominators.
  • For the same remainder, take the HCF of the differences; for a given remainder r, take LCM + r; and when each remainder is k short, take LCM − k.

Check yourself

Exam-style questions on this chapter. Pick an answer to see the explanation. 0 of 28 answered

  1. How many factors does 480 have?

  2. How many factors does 72 have?

  3. How many factors does 900 have?

  4. The number 104□ is divisible by 9. What is the smallest possible value of the missing digit?

  5. The number 99□1 is divisible by 3. What is the smallest possible value of the missing digit?

  6. The number 459□ is divisible by 3. What is the smallest possible value of the missing digit?

  7. The number 17□7 is divisible by 3. What is the smallest possible value of the missing digit?

  8. Find the HCF of 99 and 63.

  9. Find the HCF of 792 and 108.

  10. Find the HCF of 99 and 45.

  11. Find the HCF of 264 and 168.

  12. Find the LCM of 4, 6 and 10.

  13. Find the LCM of 4, 15 and 24.

  14. Find the LCM of 9, 12 and 14.

  15. Find the LCM of 9, 10 and 14.

  16. The HCF of two numbers is 4 and their LCM is 40. If one number is 8, what is the other?

  17. The HCF of two numbers is 12 and their LCM is 264. If one number is 24, what is the other?

  18. Find the largest number that divides 118, 352 and 451 leaving the same remainder in each case.

  19. Find the largest number that divides 97, 149 and 197 leaving the same remainder in each case.

  20. Find the largest number that divides 100, 208 and 379 leaving the same remainder in each case.

  21. Find the smallest number that leaves remainders 8, 9 and 11 when divided by 15, 16 and 18.

  22. Find the smallest number that leaves remainder 6 when divided by 10, 15 and 16.

  23. Find the smallest number that leaves remainder 3 when divided by 10, 15 and 16.

  24. A floor measures 3 m 60 cm by 4 m 40 cm. What is the least number of equal square tiles that will cover it exactly?

  25. A floor measures 1 m 80 cm by 2 m 52 cm. What is the least number of equal square tiles that will cover it exactly?

  26. A floor measures 2 m 70 cm by 3 m 30 cm. What is the least number of equal square tiles that will cover it exactly?

  27. Three bells ring every 6, 8 and 15 minutes. They ring together at 9:00. When will they next ring together?

  28. Three bells ring every 6, 15 and 18 minutes. They ring together at 9:00. When will they next ring together?

Previous year questions

Previous year questions for UPSC CSE will appear here once each one is checked word for word against the official question paper.

Frequently asked questions

What is the divisibility rule for 11?

The difference between the sums of digits in odd and even places must be 0 or a multiple of 11.

How do you count the factors of a number?

Write N = pᵃ × qᵇ × rᶜ; the number of factors is (a + 1)(b + 1)(c + 1).

What is the relation between HCF and LCM?

For two numbers a and b, HCF × LCM = a × b.

How do you find the HCF of fractions?

HCF of numerators divided by LCM of denominators; the LCM of fractions is LCM of numerators divided by HCF of denominators.