Question

Use Euclids division algorithm to find the HCF of $441,567,693.$

Answer 1

The Euclidean Algorithm for finding HCF $(A,B)$ is as follows:

If $A=0$ then HCF $(A,B)=B,$ since the HCF $(0,B)=B,$ and we can stop.

If $B=0$ then HCF $(A,B)=A,$ since the HCF $(A,0)=A,$ and we can stop.

Write $A$ in quotient remainder form $(A=BQ+R)$

Find HCF $(B,R)$ using the Euclidean Algorithm since

HCF $(A,B)=HCF(B,R)$

Here, HCF of $441$ and $567$ can be found as follows:-

$567=441\times 1+126$

$\Rightarrow$ $441=126\times 3+63$

$\Rightarrow$ $126=63\times 2+0$

Since remainder is $0$, therefore,

H.C.F of $(441,567)$ is $=63$

Now H.C.F of $63$ and $693$ is

$693=63\times 11+0$

Therefore, H.C.F of $(63,693)=63$

Thus, H.C.F of $(441,567,693)=63.$