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

Question

Philoid · Accepted Answer

By Euclid’s division algorithm, b = a × q + r, 0 ≤ r < a

Here, b is any positive integer .

First we take b = 693 and a = 567 and get the required HCF.

⇒ 693 = 567 × 1 + 126

⇒ 567 = 126 × 4 + 63

⇒ 126 = 63 × 2 + 0

So, HCF(693,567) = 63

Now, take b = 441 and a = 63 and get the required HCF.

⇒ 441 = 63 × 7 + 0

So, HCF (441, 63) = 63

Hence, the HCF (441, 567, 693) = 63