Question

use Euclids division algorithm to find the HCF of 441, 567, 693

Answer 1

Solution -

Euclid's division Lemma (algorithm) to fine HCF of (441, 567, 693)

Consider a = 693    b = 567  and   c = 441

By Euclid's division lemma,

a = bq + r        (as dividend = divisor * quotient + remainder)

First consider two numbers a = 693 and b = 567

693 = 567 * 1 + 126               (r not equals to 0)

567 = 126 * 4 + 63                  (r not equals to 0)

126 = 63 * 2 + 0                      ( r is equal to 0)

Stop here.

HCF of 693, 567 = 63.

Now find HCF of (441, 63)

where c = 441 and assume d = 63

Again apply Euclid's division lemma 

c = dq + r

441 = 63 * 7 + 0                (r is equal to 0)

Therefore, HCF of 441 and 63 is 63.

Therefore, HCF of 441, 567 and 693 is 63.