Question:
Use Euclid’s division algorithm to find the HCF of 441, 567 and 693.
Solution:
Let a = 693, b = 567 and c = 441 By Euclid’s division algorithms,
$a=b q+r$ $\ldots(1)$
$[\because$ dividend $=$ divisor $\times$ quotient $+$ remainder $]$
First we take, $a=693$ and $b=567$ and find their HCF.
$693=567 \times 1+126$
$567=126 \times 4+63$
$126=63 \times 2+0$
$\therefore \quad \operatorname{HCF}(693,567)=63$
Now, we take $c=441$ and say $d=63$, then find their HCF. Again, using Euclid's division algorithm,
$c=d q+r$
$\Rightarrow \quad 441=63 \times 7+0$
$\therefore \quad \operatorname{HCF}(693,567,441)=63$