Question

Use Euclid's division algorithm to find HCF of $399$ and $56$​.

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.

$$\begin{gathered} 399=56\times 7+7 \\ 56=7\times 8+0 \end{gathered}$$

The quotient is $7$

So the HCF of $(399,56)=7$