Use Euclid’s division algorithm

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$

Leave a comment