Question:
Use Euclid's algorithm to find the HCF of 441, 567 and 693.
Solution:
Let us first find the HCF of 441 and 567 using Euclid's division lemma.
441 < 567
Thus, we divide 567 by 441 by using Euclid's division lemma
567 = 441 × 1 + 126
∵ Remainder is not zero,
∴ we divide 441 by 126 by using Euclid's division lemma
441 = 126 × 3 + 63
∵ Remainder is not zero,
∴ we divide 126 by 63 by using Euclid's division lemma
126 = 63 × 2 + 0
Since, Remainder is zero,
Therefore, HCF of 441 and 567 is 63.
Now, let us find the HCF of 693 and 63 using Euclid's division lemma.
693 > 63
Thus, we divide 693 by 63 by using Euclid's division lemma
693 = 63 × 11 + 0
Since, Remainder is zero,
Therefore, HCF of 693 and 63 is 63.
Hence, the HCF of 441, 567 and 693 is 63.