Find the HCF of 96 and 404 using Euclid's division algorithm.
Reveal answerHide answer▾
What it is
Euclid's algorithm finds the HCF by repeated division until the remainder becomes zero.
Answer
Apply repeated division: 404 = 96 x 4 + 20; 96 = 20 x 4 + 16; 20 = 16 x 1 + 4; 16 = 4 x 4 + 0. The last non-zero remainder is 4, so HCF(96, 404) = 4.
a = bq + r, then HCF(a,b) = HCF(b,r)
- •404 = 96 x 4 + 20
- •96 = 20 x 4 + 16
- •20 = 16 x 1 + 4
- •16 = 4 x 4 + 0 -> HCF = 4
Why learn this
HCF simplifies fractions, shares things equally and even underpins computer cryptography (RSA).
💡 Memory trick
Divide, take the remainder, divide again. Last non-zero remainder = HCF.