Question

Using Euclid’s division algorithm to find the HCF of 4052 and 12576.

Answer 1

Hint: To solve this you have to be familiar with Euclid’s lemma as we use this lemma by dividing the largest number with the smallest one until we get the remainder zero.

Complete step-by-step answer:
Now first we understand what is Euclid’s division algorithm:
It is the process of applying Euclid’s division lemma several times to obtain the HCF of any two numbers.
Let a and b be two numbers, such that a > b
According to Euclid’s division lemma we get two integers q(quotient) and r(remainder)
i.e. a = b x q + r

Now any common factor of a and b must also be a factor of r. Let k is a common factor of both a and b
Drive the above relation on both sides by k
We have,
$\dfrac{a}{k} = \dfrac{b}{k}\left( q \right) + \dfrac{r}{k}$
Clearly the left side is an integer which means the right side must also be an integer.
Thus, r must be divisible by k Now here in this equation
12576 > 4052

Now applying Euclid’s division lemma, we get
\[4052\mathop{\left){\vphantom{1\begin{gathered}
  12576 \\
  \underline {12156} \\
  420 \\
\end{gathered} }}\right.
\!\!\!\!\overline{\,\,\,\vphantom 1{\begin{gathered}
  12576 \\
  \underline {12156} \\
  420 \\
\end{gathered} }}}
\limits^{\displaystyle \,\,\, 3}\]
Or \[12576 = 4052 \times 3 + 420\]
Now, 4052 > 420

Applying Euclid’s division lemma, we get
\[420\mathop{\left){\vphantom{1\begin{gathered}
  4052 \\
  \underline {3780} \\
  272 \\
\end{gathered} }}\right.
\!\!\!\!\overline{\,\,\,\vphantom 1{\begin{gathered}
  4052 \\
  \underline {3780} \\
  272 \\
\end{gathered} }}}
\limits^{\displaystyle \,\,\, 9}\]
Or \[4052 = 420 \times 9 + 272\]
Now 420 > 272

Applying Euclid’s division lemma, we get
\[272\mathop{\left){\vphantom{1\begin{gathered}
  420 \\
  \underline {272} \\
  148 \\
\end{gathered} }}\right.
\!\!\!\!\overline{\,\,\,\vphantom 1{\begin{gathered}
  420 \\
  \underline {272} \\
  148 \\
\end{gathered} }}}
\limits^{\displaystyle \,\,\, 1}\]
\[420 = 272 \times 1 + 148\]
Now 272 > 148

Applying Euclid’s division lemma, we get
\[148\mathop{\left){\vphantom{1\begin{gathered}
  272 \\
  \underline {148} \\
  124 \\
\end{gathered} }}\right.
\!\!\!\!\overline{\,\,\,\vphantom 1{\begin{gathered}
  272 \\
  \underline {148} \\
  124 \\
\end{gathered} }}}
\limits^{\displaystyle \,\,\, 1}\]
\[272 = 148 \times 1 + 124\]
Now 148 > 124

Applying Euclid’s division lemma, we get
\[24\mathop{\left){\vphantom{1\begin{gathered}
  124 \\
  \underline {120} \\
  4 \\
\end{gathered} }}\right.
\!\!\!\!\overline{\,\,\,\vphantom 1{\begin{gathered}
  124 \\
  \underline {120} \\
  4 \\
\end{gathered} }}}
\limits^{\displaystyle \,\,\, 5}\]
Or \[124 = 24 \times 5 + 4\]
Now 24 > 4

Applying Euclid’s division lemma, we get
\[4\mathop{\left){\vphantom{1\begin{gathered}
  24 \\
  \underline {24} \\
  0 \\
\end{gathered} }}\right.
\!\!\!\!\overline{\,\,\,\vphantom 1{\begin{gathered}
  24 \\
  \underline {24} \\
  0 \\
\end{gathered} }}}
\limits^{\displaystyle \,\,\, 6}\]
\[24 = 4 \times 6 + 0\]

Now the remainder has become zero so the procedure stops. Now the divisor at the stage is 4 therefore the HCF of 12576 and 4052 is 4

NOTE: In these types of questions we have to identify the largest number between the two and then divide the largest one from another given number. Until the remainder becomes zero as we have solved in this given problem.