• 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

  1. Divide the larger number by the smaller.
  2. If the remainder is 0, the smaller number is the HCF.
  3. Otherwise, divide the previous divisor by the remainder.
  4. 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

  1. Divide Divide the larger number by the smaller.
  2. Look at the remainder If it is 0, the divisor is the HCF.
  3. Swap the pair Otherwise, divide the previous divisor by the remainder.

Then back to step 1: Divide

When the remainder is 0, the last divisor used is the HCF.

Worked example 1: HCF of 391 and 667

StepDivisionRemainder
1667 = 1 × 391 + 276276
2391 = 1 × 276 + 115115
3276 = 2 × 115 + 4646
4115 = 2 × 46 + 2323
546 = 2 × 23 + 00

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

  1. 667 = 1 × 391 + 276
  2. 391 = 1 × 276 + 115
  3. 276 = 2 × 115 + 46
  4. 115 = 2 × 46 + 23
  5. 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.

Ladder for 12, 15, 20 and 27: each row is divided by the divisor beside it
DivisorNumbers in the row
212, 15, 20, 27
26, 15, 10, 27
33, 15, 5, 27
51, 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. 1. Using the division method, what is the HCF of 437 and 551?

    1. 19
    2. 23
    3. 29
    4. 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. 2. In the division method for the HCF, when do you stop, and what is the answer?

    1. When the quotient is 1; the answer is the last remainder
    2. When the remainder is 0; the answer is the last divisor used
    3. When the remainder is 1; the answer is 1 more than the last quotient
    4. 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. 3. What is the HCF of 1,001 and 1,183?

    1. 7
    2. 13
    3. 143
    4. 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. 4. Using the ladder method, what is the LCM of 8, 12, 18 and 30?

    1. 180
    2. 720
    3. 360
    4. 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. 5. What is the HCF of 168, 252 and 420?

    1. 42
    2. 84
    3. 126
    4. 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.

Privacy · Terms · Refunds · Delivery