Question

Use Euclid's division algorithm to find the $HCF$ of the following number: $237$ and $81$

Answer 1

Since $237>81$, we apply the division lemma to $237$ and $81$ to obtain:

$237=81\times 2+75$

Since remainder $75\ne 0$, we apply the division lemma to $81$ and $75$ to obtain:

$81=75\times 1+6$

We consider the new divisor $75$ and new remainder $6$, and apply the division lemma to obtain

$75=6\times 12+3$

Now, the new divisor is $6$ and new remainder is $3$, and apply the division lemma to obtain

$6=3\times 2+0$

Since the remainder is zero, the process stops.

Also, the divisor at this stage is $3$,

Hence, the $HCF$ of $237$ and $81$ is $3$.