Question

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

Answer 1

Let a = 693, b = 567 and c = 441

By Euclid’s division algorithm,

a = bq + r   ...(i)  [∵ Dividend = Divisor × Quotient + Remainder]

First we take, a = 693 and b = 567 and find their HCF.

693 = 567 × 1 + 126

567 = 126 × 4 + 63

126 = 63 × 2 + 0

∴ HCF(693, 567) = 63

Now, we take c = 441 and (say) d = 63, then find their HCF.

Again, using Euclid’s division algorithm, c = dq + r

`\implies` 441 = 63 × 7 + 0

∴ HCF(693, 567, 441) = 63