Question

Find the HCF of the following numbers using Division Lemma.
(1) 455, 42 (2) 196, 38220
(3) 867, 255 (4) 306, 657
(5) 510, 92 (6) 4052, 12576

Answer 1

Hint: For solving this question first we will see the concept of Euclid Division Lemma. After that, we will see how we can use it in the Euclid Division Algorithm to find the HCF of any two numbers. Then, we will solve each part separately to find the HCF of the given numbers.

Complete step-by-step solution -
Given:
We have to find the HCF of the following numbers using Division Lemma:
(1) 455, 42 (2) 196, 38220
(3) 867, 255 (4) 306, 657
(5) 510, 92 (6) 4052, 12576
Now, before we proceed we should know that if $a$ is a positive integer and when we divide another positive integer $b$ by $a$ and it leaves remainder $r$ where, $r < a < b$ . Then, $b=aq+r$ where $q$ is any integer. This is also known as “Euclid Division Lemma”.
Now, we will see “Euclid Division Algorithm” to find HCF of any two numbers.
Euclid Division Algorithm:
Consider we have two numbers 78 and 980 and we have to find the HCF of both of these numbers. To do this, we choose the largest integer first, i.e. 980 and then according to Euclid Division Lemma, $b=aq+r$ where $0\le r < a$ . Then,
$78\overset{12}{\overline{\left){\begin{align}
  & 980 \\
 & \underline{78} \\
 & 200 \\
 & \underline{156} \\
 & \underline{044} \\
\end{align}}\right.}}$
Now, here $b=980$ , $a=78$ , $q=12$ and $r=44$ so, we can write $980=78\times 12+44$ .
Now, consider the divisor 78 and the remainder 44 and apply Euclid Division Lemma again. Then,
$44\overset{1}{\overline{\left){\begin{align}
  & 78 \\
 & \underline{44} \\
 & \underline{34} \\
\end{align}}\right.}}$
Now, here $b=78$ , $a=44$ , $q=1$ and $r=34$ so, we can write $78=44\times 1+34$ .
Now, consider the divisor 44 and the remainder 34 and apply Euclid Division Lemma again. Then,
$34\overset{1}{\overline{\left){\begin{align}
  & 44 \\
 & \underline{34} \\
 & \underline{10} \\
\end{align}}\right.}}$
Now, here $b=44$ , $a=34$ , $q=1$ and $r=10$ , so we can write $44=34\times 1+10$ .
Now, consider the divisor 34 and the remainder 10 and apply Euclid Division Lemma again. Then,
$10\overset{3}{\overline{\left){\begin{align}
  & 34 \\
 & \underline{30} \\
 & \\
\end{align}}\right.}}$
Now, here $b=34$ , $a=10$ , $q=3$ and $r=4$ , so we can write $34=10\times 3+4$ .
Now, consider the divisor 10 and the remainder 4 and apply Euclid Division Lemma again. Then,
$4\overset{2}{\overline{\left){\begin{align}
  & 10 \\
 & \underline{08} \\
 & \underline{02} \\
\end{align}}\right.}}$
Now, here $b=10$ , $a=4$ , $q=2$ and $r=2$ so, we can write $10=4\times 2+2$ .
Now, consider the divisor 4 and the remainder 2 and apply Euclid Division Lemma again. Then,
$2\overset{2}{\overline{\left){\begin{align}
  & 4 \\
 & \underline{4} \\
 & \underline{0} \\
\end{align}}\right.}}$
Now, as we see that the remainder has become zero, therefore, proceeding further is not possible and hence the HCF is the divisor $a=2$ left in the last step. And we can say that the HCF of 980 and 78 is 2.
Now, we will find the HCF of each part separately.

(1) 455, 42
Now, applying the Euclid Division Lemma. Then,
$42\overset{10}{\overline{\left){\begin{align}
  & 455 \\
 & \underline{42\text{ }} \\
 & \underline{035} \\
\end{align}}\right.}}$
Now, here $b=455$ , $a=42$ , $q=10$ and $r=35$ , so we can write $455=42\times 10+35$ .
Now, consider the divisor 42 and the remainder 35 and apply Euclid Division Lemma again. Then,
$35\overset{1}{\overline{\left){\begin{align}
  & 42 \\
 & \underline{35} \\
 & \underline{07} \\
\end{align}}\right.}}$
Now, here $b=42$ , $a=35$ , $q=1$ and $r=7$ so, we can write $42=35\times 1+7$ .
Now, consider the divisor 35 and the remainder 7 and apply Euclid Division Lemma again. Then,
$7\overset{5}{\overline{\left){\begin{align}
  & 35 \\
 & \underline{35} \\
 & \underline{00} \\
\end{align}}\right.}}$
Now, as we see that the remainder has become zero, therefore, proceeding further is not possible and hence the HCF is the divisor $a=7$ left in the last step. And we can say that the HCF of 455 and 42 is 7.
(2) 196, 38220
Now, applying the Euclid Division Lemma. Then,
\[196\overset{195}{\overline{\left){\begin{align}
  & 38220 \\
 & \underline{196} \\
 & 18620 \\
 & \underline{1764} \\
 & 00980 \\
 & \underline{00980} \\
 & \underline{00000} \\
\end{align}}\right.}}\]
Now, as we see that the remainder has become zero, therefore, proceeding further is not possible and hence the HCF is the divisor $a=196$ left in the last step. And we can say that the HCF of 196 and 38220 is 196.
(3) 867, 255
Now, applying the Euclid Division Lemma. Then,
$255\overset{3}{\overline{\left){\begin{align}
  & 867 \\
 & \underline{765} \\
 & \underline{102} \\
\end{align}}\right.}}$
Now, here $b=867$ , $a=255$ , $q=3$ and $r=102$ so, we can write $867=255\times 3+102$ .
Now, consider the divisor 255 and the remainder 102 and apply Euclid Division Lemma again. Then,
$102\overset{2}{\overline{\left){\begin{align}
  & 255 \\
 & \underline{204} \\
 & \underline{051} \\
\end{align}}\right.}}$
Now, here $b=255$ , $a=102$ , $q=2$ and $r=51$ so, we can write $867=255\times 3+102$ .
Now, consider the divisor 255 and the remainder 102 and apply Euclid Division Lemma again. Then,
\[51\overset{2}{\overline{\left){\begin{align}
  & 102 \\
 & \underline{102} \\
 & \underline{000} \\
\end{align}}\right.}}\]
Now, as we see that the remainder has become zero, therefore, proceeding further is not possible and hence the HCF is the divisor $a=51$ left in the last step. And we can say that the HCF of 867 and 255 is 51.
(4) 306, 657
Now, applying the Euclid Division Lemma. Then,
$306\overset{2}{\overline{\left){\begin{align}
  & 657 \\
 & \underline{612} \\
 & \underline{045} \\
\end{align}}\right.}}$
Now, here $b=657$ , $a=306$ , $q=2$ and $r=45$ so, we can write $657=306\times 2+45$ .
Now, consider the divisor 306 and the remainder 45 and apply Euclid Division Lemma again. Then,
$45\overset{6}{\overline{\left){\begin{align}
  & 306 \\
 & \underline{270} \\
 & \underline{036} \\
\end{align}}\right.}}$
Now, here $b=306$ , $a=45$ , $q=6$ and $r=36$ , so we can write $306=45\times 6+36$ .
Now, consider the divisor 45 and the remainder 36 and apply Euclid Division Lemma again. Then,
$36\overset{1}{\overline{\left){\begin{align}
  & 45 \\
 & \underline{36} \\
 & \underline{09} \\
\end{align}}\right.}}$
Now, here $b=45$ , $a=36$ , $q=1$ and $r=9$ , so we can write $45=36\times 1+9$ .
Now, consider the divisor 36 and the remainder 9 and apply Euclid Division Lemma again. Then,
\[9\overset{4}{\overline{\left){\begin{align}
  & 36 \\
 & \underline{36} \\
 & \underline{00} \\
\end{align}}\right.}}\]
Now, as we see that the remainder has become zero, therefore, proceeding further is not possible and hence the HCF is the divisor $a=9$ left in the last step. And we can say that the HCF of 306 and 657 is 9.
(5) 510, 92
Now, applying the Euclid Division Lemma. Then,
$92\overset{5}{\overline{\left){\begin{align}
  & 510 \\
 & \underline{460} \\
 & \underline{050} \\
\end{align}}\right.}}$
Now, here $b=510$ , $a=92$ , $q=5$ and $r=50$ , so we can write $510=92\times 5+50$ .
Now, consider the divisor 92 and the remainder 50 and apply Euclid Division Lemma again. Then,
$50\overset{1}{\overline{\left){\begin{align}
  & 92 \\
 & \underline{50} \\
 & \underline{42} \\
\end{align}}\right.}}$
Now, here $b=92$ , $a=50$ , $q=1$ and $r=42$ so, we can write $92=50\times 1+42$ .
Now, consider the divisor 50 and the remainder 42 and apply Euclid Division Lemma again. Then,
$42\overset{1}{\overline{\left){\begin{align}
  & 50 \\
 & \underline{42} \\
 & \underline{08} \\
\end{align}}\right.}}$
Now, here $b=50$ , $a=42$ , $q=1$ and $r=8$ , so we can write $50=42\times 1+8$ .
Now, consider the divisor 42 and the remainder 8 and apply Euclid Division Lemma again. Then,
$8\overset{5}{\overline{\left){\begin{align}
  & 42 \\
 & \underline{40} \\
 & \underline{02} \\
\end{align}}\right.}}$
Now, here $b=42$ , $a=8$ , $q=5$ and $r=2$ so, we can write $42=8\times 5+2$ .
Now, consider the divisor 8 and the remainder 2 and apply Euclid Division Lemma again. Then,
$2\overset{4}{\overline{\left){\begin{align}
  & 8 \\
 & \underline{8} \\
 & \underline{0} \\
\end{align}}\right.}}$
Now, as we see that the remainder has become zero, therefore, proceeding further is not possible and hence the HCF is the divisor $a=2$ left in the last step. And we can say that the HCF of 510 and 92 is 2.
(6) 4052, 12576
Now, applying the Euclid Division lemma. Then,
$4052\overset{3}{\overline{\left){\begin{align}
  & 12576 \\
 & \underline{12156} \\
 & \underline{00420} \\
\end{align}}\right.}}$
Now, here $b=12576$ , $a=4052$ , $q=3$ and $r=420$ so, we can write $12576=4052\times 3+420$ .
Now, consider the divisor 4052 and the remainder 420 and apply Euclid Division Lemma again. Then,
$420\overset{9}{\overline{\left){\begin{align}
  & 4052 \\
 & \underline{3780} \\
 & \underline{0272} \\
\end{align}}\right.}}$
Now, here $b=4052$ , $a=420$ , $q=9$ and $r=272$ so, we can write $4052=420\times 9+272$ .
Now, consider the divisor 420 and the remainder 272 and apply Euclid Division Lemma again. Then,
$272\overset{1}{\overline{\left){\begin{align}
  & 420 \\
 & \underline{272} \\
 & \underline{148} \\
\end{align}}\right.}}$
Now, here $b=420$ , $a=272$ , $q=1$ and $r=148$ , so we can write $420=272\times 1+148$ .
Now, consider the divisor 272 and the remainder 148 and apply Euclid Division Lemma again. Then,
$148\overset{1}{\overline{\left){\begin{align}
  & 272 \\
 & \underline{148} \\
 & \underline{124} \\
\end{align}}\right.}}$
Now, here $b=272$ , $a=142$ , $q=1$ and $r=124$ , so we can write $272=148\times 1+124$ .
Now, consider the divisor 148 and the remainder 124 and apply Euclid Division Lemma again. Then,
$124\overset{1}{\overline{\left){\begin{align}
  & 148 \\
 & \underline{124} \\
 & \underline{024} \\
\end{align}}\right.}}$
Now, here $b=148$ , $a=124$ , $q=1$ and $r=24$ , so we can write $148=124\times 1+24$ .
Now, consider the divisor 124 and the remainder 24 and apply Euclid Division Lemma again. Then,
$24\overset{5}{\overline{\left){\begin{align}
  & 124 \\
 & \underline{120} \\
 & \underline{004} \\
\end{align}}\right.}}$
Now, here $b=124$ , $a=24$ , $q=1$ and $r=4$ , so we can write $124=24\times 5+4$ .
Now, consider the divisor 24 and the remainder 4 and apply Euclid Division Lemma again. Then,
$4\overset{6}{\overline{\left){\begin{align}
  & 24 \\
 & \underline{24} \\
 & \underline{00} \\
\end{align}}\right.}}$
Now, as we see that the remainder has become zero, therefore, proceeding further is not possible and hence the HCF is the divisor $a=4$ left in the last step. And we can say that the HCF of 4052 and 12576 is 4.

Note: Here, the student should first understand what is asked in the problem and then proceed in the right direction to prove the desired result. After that, we should apply the result of the Euclid Division Lemma correctly and use proper numerical examples for better understanding then, proceed stepwise without any confusion. Moreover, we should use the long division method for better clarity of the concept at each step.