Question

Use Euclid's algorithm to find the HCF of 441, 567 and 693.

Answer 1

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.