Question

Use Euclid's division algorithm to find the H.C.F. of $196$ and $38318$

Answer 1

While applying Euclid's division lemma for finding H.C.F. of say $c$ & $d$ we proceed through the following steps:

1. Find whole numbers $q$ and $r$ such that $c=dq+r$..............$0\le r<d$
2. If $r=0$, then $d$ is $H.C.F.$
If $r\ne 0$, then continue division until remainder or $r$ becomes $0$, thus divisor or $d$ becoming $H.C.F.$

Applying Euclid’s division lemma to $196$ and $38318.$

$38318=196\times 195+98$

$196=98\times 2+0$

The remainder at the second stage is zero $\left(0\right)$

So, the H.C.F. of $38318$ and $196$ is $98.$