Use Euclid's division algorithm


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


Here we have to find the HCF of the numbers 10224 and 9648 by using Euclid’s division algorithm.

We know that If we divide a by b and r is the remainder and is the quotient, Euclid’s Lemma says that

$A=b q+r$, where $0 \leq r

And HCF of (a, b) = HCF of (b, r)

Here $a=10224$ and $b=9648$

Therefore, we have the following procedure,

$10224=9648 \times 1+576$

Now, we apply the division algorithm on 9648 and 576.

$9648=576 \times 16+432$

$\Rightarrow 576=432 \times 1+144$


$\Rightarrow 432=144 \times 3+0$

Therefore the HCF of 432 and 144 is 144.

Hence the HCF of 10224 and 9648 is 144


Leave a comment