- Foundation
- About 14 min
- 5 practice questions
The division method for HCF and the ladder method for LCM
Find the HCF of large numbers by repeated division and the LCM of several numbers by the ladder (common division) method, without listing every factor.
If something looks wrong, please tell us.
Prime factorisation is slow when a number hides a large prime factor. Try factorising 391 quickly: it is 17 × 23, which is not obvious. The division method (Euclid's method) finds the HCF without factorising anything, and the ladder method gives the LCM of several numbers in one neat table.
The division method for HCF
- Divide the larger number by the smaller.
- If the remainder is 0, the smaller number is the HCF.
- Otherwise, divide the previous divisor by the remainder.
- Repeat until the remainder is 0. The last divisor used is the HCF.
It works because any number that divides both a and b also divides a − b, and so also the remainder when a is divided by b. Each step swaps the pair for a smaller pair with the same HCF, until only the answer is left.
The division method for HCF
- Divide Divide the larger number by the smaller.
- Look at the remainder If it is 0, the divisor is the HCF.
- Swap the pair Otherwise, divide the previous divisor by the remainder.
Then back to step 1: Divide
Worked example 1: HCF of 391 and 667
| Step | Division | Remainder |
|---|---|---|
| 1 | 667 = 1 × 391 + 276 | 276 |
| 2 | 391 = 1 × 276 + 115 | 115 |
| 3 | 276 = 2 × 115 + 46 | 46 |
| 4 | 115 = 2 × 46 + 23 | 23 |
| 5 | 46 = 2 × 23 + 0 | 0 |
The last divisor is 23, so HCF = 23. Check: 391 = 17 × 23 and 667 = 29 × 23. Factorisation would have needed you to spot 17, 23 and 29; the division method needed only simple division.
HCF of 391 and 667
- 667 = 1 × 391 + 276
- 391 = 1 × 276 + 115
- 276 = 2 × 115 + 46
- 115 = 2 × 46 + 23
- 46 = 2 × 23 + 0 The last divisor is 23, so HCF = 23.
HCF of three or more numbers
Find the HCF of the first two, then the HCF of that answer and the third number, and so on. Worked example 2: HCF of 144, 252 and 396. First 144 and 252: 252 = 1 × 144 + 108; 144 = 1 × 108 + 36; 108 = 3 × 36 + 0, so HCF(144, 252) = 36. Then 36 and 396: 396 = 11 × 36 + 0, so the HCF of all three is 36.
The ladder method for LCM
Write the numbers in a row. Divide by a prime that divides at least two of them; write each quotient below, and bring down unchanged any number that is not divisible. Repeat until no prime divides two of the numbers left. The LCM is the product of all the divisors on the left and all the numbers in the last row.
Worked example 3: LCM of 12, 15, 20 and 27.
| Divisor | Numbers in the row |
|---|---|
| 2 | 12, 15, 20, 27 |
| 2 | 6, 15, 10, 27 |
| 3 | 3, 15, 5, 27 |
| 5 | 1, 5, 5, 9 |
| (last row) | 1, 1, 1, 9 |
LCM = 2 × 2 × 3 × 5 × 9 = 540. Check with primes: 12 = 2² × 3, 15 = 3 × 5, 20 = 2² × 5 and 27 = 3³, so LCM = 2² × 3³ × 5 = 4 × 27 × 5 = 540.
One caution: the ladder gives the LCM, not the HCF. The HCF is only the product of the divisors that divided every number in their row. In this example no divisor divided all four numbers, so the HCF of 12, 15, 20 and 27 is 1.
Division method: divide, then divide the divisor by the remainder; the last divisor is the HCF. Ladder method: LCM = product of the divisors × the numbers left in the last row.
Key takeaways: use the division method when the numbers are large or hard to factorise; it never needs you to spot a prime. For three or more numbers, find the HCF two at a time. Use the ladder method to get the LCM of several numbers in one go, and always check that the answer is a multiple of every number.
Check your understanding
-
1. Using the division method, what is the HCF of 437 and 551?
- 19
- 23
- 29
- 38
Show answer
Answer: A. 551 = 1 × 437 + 114; 437 = 3 × 114 + 95; 114 = 1 × 95 + 19; 95 = 5 × 19 + 0. The last divisor is 19, so the HCF is 19. (437 = 19 × 23 and 551 = 19 × 29.)
-
2. In the division method for the HCF, when do you stop, and what is the answer?
- When the quotient is 1; the answer is the last remainder
- When the remainder is 0; the answer is the last divisor used
- When the remainder is 1; the answer is 1 more than the last quotient
- After exactly three divisions; the answer is the last quotient
Show answer
Answer: B. You keep dividing the previous divisor by the remainder until a division leaves remainder 0. The divisor in that final division is the HCF. If a remainder of 1 appears, the next division is by 1 and leaves 0, so the HCF is 1.
-
3. What is the HCF of 1,001 and 1,183?
- 7
- 13
- 143
- 91
Show answer
Answer: D. 1,183 = 1 × 1,001 + 182; 1,001 = 5 × 182 + 91; 182 = 2 × 91 + 0. The last divisor is 91, so the HCF is 91. (1,001 = 7 × 11 × 13 and 1,183 = 7 × 13 × 13.)
-
4. Using the ladder method, what is the LCM of 8, 12, 18 and 30?
- 180
- 720
- 360
- 1,080
Show answer
Answer: C. Divide by 2: 4, 6, 9, 15. Divide by 2 again: 2, 3, 9, 15. Divide by 3: 2, 1, 3, 5. No prime now divides two of 2, 1, 3 and 5. LCM = 2 × 2 × 3 × 2 × 1 × 3 × 5 = 360.
-
5. What is the HCF of 168, 252 and 420?
- 42
- 84
- 126
- 28
Show answer
Answer: B. HCF(168, 252): 252 = 1 × 168 + 84; 168 = 2 × 84 + 0, so it is 84. HCF(84, 420): 420 = 5 × 84 + 0, so it is 84. The HCF of all three is 84.
Sign in to keep track of the lessons you finish.