Question

Find the HCF of the following by using Euclid algorithm.
$96$ and $72$.

Answer 1

Euclid algorithm $a=bq+r$
$a>b$ and $0⩽r<b$.
$96$ and $72$
The positive integers are $96$ and $72$, $96>72$
Apply Euclid algorithm to $96$ and $72$,
$\therefore 96=(72\ast 1)+24$
The remainder is $24$.
Apply Euclid's algorithm to $72$ and $24$,
$\therefore 72=(24\ast 3)+0$
The remainder is zero.
$\therefore$ HCF of $96$ and $72$ is $24$.