UKPSC RO / ARO · Module 50 · standard depth · 19 min
Divisibility, factors, HCF and LCM
What UKPSC RO / ARO asks from this chapter
Syllabus lines this chapter covers:
- Prelims: General Studies (100) and General Aptitude Test (50) · General Aptitude Test: verbal and non-verbal reasoning, analogies, space visualisation, problem solving, decision making, number series, arithmetical computation
UKPSC RO / ARO has asked 1 question from this chapter (2023); 8 from its whole module.
Cut to standard depth for UKPSC RO / ARO. 8 deeper paragraphs are in the full chapter.
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.
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.
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.
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.
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.
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.
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.
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.
Practice set: twelve solved problems
Try each problem first, then read the steps. The problems go from easy to hard.
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
- 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.
UKPSC RO / ARO questions from this chapter
If six digits number 35A79B is divisible by 9, then value of A + B is equal to :
- (a) 12
- (b) 21
- (c) 30
- (d) 39
Show answer
(a) 12 · our answer; official key awaited