Question

Use Euclid's division algorithm to find the HCF of $10224$ and $9648$.

Answer 1

Concept: Apply Euclid’s division lemma, to $c$ and $d$. So, we find whole numbers, $q$ and $r$ such that

$c=dq+r,0\le r<d$.

If $r=0$, $d$ is the HCF of $c$ and $d.$ If $r\ne 0$, apply the division lemma to $d$ and $r$.

HCF of $10224$ and $9648$ :

$10224=(9648\times 1)+576$

$9648=(576\times 16)+432$

$576=(432\times 1)+144$

$432=(144\times 3)+0$

$\therefore$ HCF of $10224$ and $9648$ is $144$.