The continued division method, also known as Euclid's algorithm, finds the Highest Common Factor (HCF) or Greatest Common Divisor (GCD) of two numbers by repeatedly dividing the larger number by the smaller number and then replacing the larger number with the remainder until the remainder is zero. The last non-zero divisor is the HCF.
Here's a breakdown of the steps involved:
-
Divide the larger number by the smaller number.
-
Note the remainder.
-
If the remainder is zero, the smaller number is the HCF. You're done!
-
If the remainder is not zero, make the remainder the new divisor and the previous divisor the new dividend. In other words, divide the previous divisor by the remainder.
-
Repeat steps 2-4 until the remainder is zero. The last non-zero divisor is the HCF.
Example:
Let's find the HCF of 48 and 18 using the continued division method:
- Divide 48 by 18: 48 ÷ 18 = 2 remainder 12
- Divide 18 by 12: 18 ÷ 12 = 1 remainder 6
- Divide 12 by 6: 12 ÷ 6 = 2 remainder 0
Since the remainder is now 0, the last non-zero divisor (which was 6) is the HCF of 48 and 18. Therefore, HCF(48, 18) = 6.
Another Example:
Find the HCF of 72 and 96.
- 96 ÷ 72 = 1 remainder 24
- 72 ÷ 24 = 3 remainder 0
The last non-zero divisor is 24. Therefore, HCF(72, 96) = 24.
Why this works (brief explanation):
The basic principle behind this method is that any factor common to both numbers must also be a factor of their difference, and therefore a factor of the remainder when one is divided by the other. By repeatedly finding smaller and smaller remainders, we eventually arrive at the greatest common factor.
