Question

Using Euclid's division Lemma find the H.C.F of $441,567,693$.

Answer 1

According to Euclid’s Division Lemma if we have two positive integers $a$ and $b$, then there exist unique integers $q$ and $r$ which satisfies the condition $a=bq+r$ where $0\le r<b$. That means, on dividing both the integers $a$ and $b$ the remainder is zero.

The Euclidean Algorithm for finding H.C.F $(\mathrm{A},\mathrm{B})$ is as follows:

If $\mathrm{A}=0$ then H.C.F $(\mathrm{A},\mathrm{B})=\mathrm{B}$,

since the H.C.F $(0,\mathrm{B})=\mathrm{B}$, and we can stop.

If $\mathrm{B}=0$ then H.C.F $(\mathrm{A},\mathrm{B})=\mathrm{A}$,

since the $\mathrm{H}.\mathrm{C}.\mathrm{F}(\mathrm{A},0)=\mathrm{A}$, and we can stop.

If $A\ne 0,B\ne 0$, then write $A$ in quotient remainder form as $(\mathrm{A}=\mathrm{BQ}+\mathrm{R})$

Find H.C.F $(\mathrm{B},\mathrm{R})$ using the Euclidean Algorithm since H.C.F $(\mathrm{A},\mathrm{B})$ = H.C.F$(\mathrm{B},\mathrm{R})$

Here, H.C.F of $441$and $567$ can be found as follows:-

$$\begin{gathered} 567=441\times 1+126 \\ \Rightarrow 441=126\times 3+63 \\ \Rightarrow 126=63\times 2+0 \end{gathered}$$

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$.