Question

Use Euclids division algorithm to find the HCF of $196$ and $38220$.

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+rwhere0\le r<b$

Consider two numbers $196$ and $38220$, and we need to find the HCF of these numbers.

$\mathrm{Dividend}=\mathrm{Quotient}\times \mathrm{Divisor}+\mathrm{Remainder}$

When the reminder is zero then the quotient is the HCF.

Now, $38220>196$
Using Euclid’s division algorithm,
$38220=196\times 195+0$
Here, the remainder is $0$.
Therefore, the HCF of $196$ and $38220$ is $196$.