Use Euclid's division algorithm to find the HCF of 441 567 693

We know Euclid's division lemma:

Let a and b be any two positive integers. Then there exist two unique whole numbers q and r such that

a = b q + r,

where 0 ≤ r < b

Here, a is called the dividend,

b is called the divisor,

q is called the quotient and

r is called the remainder.

According to the problem given,

Start with 693 and 567.

Apply the division lemma,

693 = (576 × 1) + 117

Since the remainder is not equal to zero, apply lemma again on 576 and 117.

576 = (117 × 4) + 108

Since the remainder is not equal to zero, apply lemma again on 117 and 108.

117 = (108 × 1) + 9

Since the remainder is not equal to zero, apply lemma again on 108 and 9.

108 = (9 × 12) + 0

The remainder has now become zero.

⇒ HCF (693, 567) = 9

Now we have to find HCF of 9 and 441.

Similarly, apply lemma on 441 and 9.

441 = (9 × 49) + 0

Since, the remainder is equal to 0.

⇒ HCF (9, 441) = 9

Therefore, HCF (441, 567, 693) = 9.