Question

Use Euclid's division algorithm to find the HCF of $4052$ and $12576$.

Answer 1

According to Euclid’s Division Lemma if we have two positive integers $a$ and $b$, then there exist unique integers $q$ and$r$ which satisfies the condition

$a=bq+rwhere0\le r<b$

Consider two numbers $399$ and $56$, and we need to find the HCF of these numbers.

$\mathrm{Dividend}=\mathrm{Quotient}\times \mathrm{Divisor}+\mathrm{Remainder}$

When the reminder is zero then the quotient is the HCF.

Since $12576>4052$

$12576=(4052\times 3)+420$

$420$ is a reminder that is not equal to zero $(420\ne 0)$.

$4052=(420\times 9)+272$

$272$ is a reminder that is not equal to zero $(272\ne 0)$.

Now consider the new divisor $272$ and the new remainder $148$.

$272=(148\times 1)+124$

Now consider the new divisor $148$ and the new remainder $124$.

$148=(124\times 1)+24$

Now consider the new divisor $124$ and the new remainder $24$.

$124=(24\times 5)+4$

Now consider the new divisor $24$ and the new remainder $4$.

$24=(4\times 6)+0$

Reminder $=0$

Divisor $=4$

Hence, HCF of $12576$ and $4052$ is $4$.