Question

Use Euclid's division algorithm to find the HCF of the following number: 65 and 117

Answer 1

Since $117>65$, we apply the division lemma to $117$ and $65$ to obtain:

$117=65\times 1+52$

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

$65=52\times 1+13$

We consider the new divisor $52$ and new remainder $13$, and apply the division lemma to obtain

$52=13\times 4+0$

Since the remainder is zero, the process stops.

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

Hence, the $HCF$ of $117$ and $65$ is $13$.