How does Euclid's division algorithm work? Can you show it with an example?
I have to find the HCF of 867 and 255 using Euclid's division algorithm. I understand the concept but I do not know when to stop and which number is the HCF.
1 Answer
TSTushar Saxena
✓ Accepted
· 14d ago
▲ 15
Euclid's algorithm: dividend = divisor * quotient + remainder. Keep applying until remainder = 0. The last non-zero remainder is the HCF. For HCF(867, 255): 867 = 255 * 3 + 102. 255 = 102 * 2 + 51. 102 = 51 * 2 + 0. Remainder is 0, so HCF = 51 (the divisor in the last step). Verification: 867 = 51 * 17. 255 = 51 * 5. Both divisible by 51. 17 and 5 share no common factors. HCF = 51 is correct.
Log in to post your own answer or join the discussion.
No comments yet — start the discussion.