Question

Use Euclid’s algorithm to find the HCF of $408$ and $1032$.

Answer 1

Hint: By the Euclid’s algorithm, we need to divide the greater number $1032$ by the smaller number $408$ to get the values of the remainder. Then the previous divisor $408$ will become the new dividend and the remainder obtained will become the new divisor and the second division will be carried out. This process will be repeated till the value of the remainder becomes equal to zero. And the final HCF will be equal to the last non zero remainder.

Complete step by step solution:
By Euclid’s algorithm, we need to write the greater number $1032$ in terms of the smaller number $408$ as
$\Rightarrow 1032=408q+r$
So we need to divide $1032$ by $408$ as below.
\[408\overset{2}{\overline{\left){\begin{align}
  & 1032 \\
 & \underline{816} \\
 & \underline{216} \\
\end{align}}\right.}}\]
So we got the quotient as $2$ and the remainder as $216$. So from the above equation we can write
$\Rightarrow 1032=408\times 2+216$
Now, the divisor $408$ will become the new dividend and the remainder $216$ will become the new divisor so that we can write
$\Rightarrow 408=216q+r$
So we divide $408$ by $216$.
\[216\overset{1}{\overline{\left){\begin{align}
  & 408 \\
 & \underline{216} \\
 & \underline{192} \\
\end{align}}\right.}}\]
$\Rightarrow 408=216\times 1+192$
Similarly, we will divide $216$ by $192$.
\[192\overset{1}{\overline{\left){\begin{align}
  & 216 \\
 & \underline{192} \\
 & \underline{24} \\
\end{align}}\right.}}\]
$\Rightarrow 216=192\times 1+24$
\[24\overset{8}{\overline{\left){\begin{align}
  & 192 \\
 & \underline{192} \\
 & \underline{0} \\
\end{align}}\right.}}\]
$\Rightarrow 192=24\times 8+0$
So finally we obtained the remainder as zero. By Euclid's algorithm, the HCF of the given numbers will be equal to the last non zero remainder obtained. From above, we can see that the last non zero remainder is equal to $24$.
Hence, the remainder of $408$ and $1032$ is equal to $24$.

Note: We can find the HCF of the given two numbers using the prime factorization method too. But Euclid's algorithm is much easier. But we must carefully do all the divisions because if any intermediate division is performed incorrectly, then ultimately it will lead us to the incorrect answer. So if possible, confirm the value of HCF obtained using the prime factorization method.