Euclid's method for the highest common factor (HCF)
Find the highest common factor (HCF) of two numbers with a chain of divisions, without listing any factors.
- UK: Year 5
- France: grade 5
- Iran: grade 7
- Afghanistan: grade 5
- Syria: grade 5
- Palestine: grade 5
- Ukraine: grade 6
- Russia: grade 6
Guide
Listing every factor works for small numbers, but it is slow for big ones. More than 2000 years ago Euclid found a quicker way: a chain of divisions. Syrian students learn it in grade 9; it is extra for Iranian, Afghan and UK students, and a good way to go further.
Divide the bigger number by the smaller one. Then divide the divisor by the remainder. Keep going: each time, the divisor becomes the new dividend and the remainder becomes the new divisor.
Stop when the remainder is 0. The last remainder that was not 0 (the last divisor) is the highest common factor (HCF).
Why it works: any number that divides both 84 and 60 also divides 84 − 60 = 24, and the other way round. So 84 and 60 have exactly the same common factors as 60 and 24. Each division swaps the pair for a smaller one with the same highest common factor (HCF).
Every right digit turns green. If you get stuck, press “Show me this step”.