Question

Use Euclid’s division algorithm to find the HCF of 570 and 1425.

Answer 1

Hint: Solve by using Euclid’s theorem, apply division lemma to get quotient and remainder of 1425. If the remainder is zero, the HCF is the remainder. If the remainder is not zero, continue till the remainder is zero. The division at this stage will be the required HCF.

Complete step-by-step answer:

Euclid’s division algorithm is a technique to compute the highest common factor (HCF) of two given positive integers that divides integers a and b. Let a and b any two arbitrary numbers.
Let q be the quotient and r be the remainder, then
\[\begin{align}
  & a=b\left( {{q}_{1}} \right)+{{r}_{1}} \\
 & b={{r}_{1}}\left( {{q}_{2}} \right)+{{r}_{2}} \\
 & {{r}_{1}}={{r}_{2}}\left( {{q}_{3}} \right)+{{r}_{3}} \\
 & . \\
 & . \\
 & . \\
 & . \\
 & {{r}_{n-2}}={{r}_{n-1}}\left( {{q}_{n}} \right)+{{r}_{n}} \\
 & {{r}_{n-1}}={{r}_{n}}\left( {{q}_{n+1}} \right)+0 \\
\end{align}\]
Thus we get the HCF (a, b) = \[{{r}_{n}}\].
We need to show that \[{{r}_{n}}\] is the common factor of a and b. Then show that any common factor of a and b must be a factor of \[{{r}_{n}}\], which means that \[{{r}_{n}}\] is the highest common factor.
We have been given 2 numbers 50 and 1425.
1425 is the largest number among 570 and 1425.
\[\begin{align}
  & \therefore 1425=570\times 2+285 \\
 & 570=285\times 2+0 \\
\end{align}\]
Thus we got the remainder, r as zero. The HCF is the remainder in the second last step. So HCF (1425, 570) = 285.
Thus by Euclid’s division algorithm we got the HCF as 285.

Note: Sometimes you may not understand the justification of Euclid’s division algorithm, but this reasoning is good mental exercise as well as for finding the HCF quickly without prime factorization. To confirm the answer you can do long division.
\[570\overline{\left){\begin{align}
  & 1425\left| \!{\underline {\,
  2 \,}} \right. \\
 & \underline{1140} \\
 & 285\left| \!{\underline {\,
  570 \,}} \right. \left| \!{\underline {\,
  2 \,}} \right. \\
 & -\underline{570} \\
 & 0 \\
\end{align}}\right.}\]