Euclid's division: finding the HCF
Divide the bigger number by the smaller, then the smaller by the remainder, again and again. Watch each step a = bq + r until the remainder is 0, and read off the HCF of five pairs of numbers.
Core concept
For whole numbers a and b, a = bq + r with 0 ≤ r < b; the HCF of a and b is the HCF of b and r, so dividing again and again until the remainder is 0 leaves the HCF as the last divisor
Topic: Real numbers
When one whole number a is divided by a smaller one b, there is a quotient q and a remainder r, smaller than b: a = b × q + r. This is Euclid's division lemma. It has a useful property: any number that divides both a and b also divides r, so the HCF of a and b is the same as the HCF of b and r. So divide again: b by r, then that divisor by the new remainder, and so on. The numbers get smaller each time, and when the remainder is 0 the last divisor is the HCF. For 84 and 18: 84 = 18 × 4 + 12, 18 = 12 × 1 + 6, 12 = 6 × 2 + 0, so the HCF is 6.
What you will learn
- Write a division as a = bq + r with 0 ≤ r < b.
- Use repeated division (Euclid's algorithm) to find the HCF of two numbers.
- Explain why the HCF of a and b equals the HCF of b and r.
Before you start
- Know how to divide whole numbers and find a remainder.
Materials
- A notebook and a pencil
Equipment
- None
Procedure
- Record the pair 84 and 18 and read the steps.
- Record the pairs 225 and 135, and 96 and 72.
- Record the pairs 455 and 42, and 867 and 255.
How this simulation is simplified
- a is bigger than b, and both are whole numbers.