Question

Use Euclid’s division algorithm to find HCF of:
a) 169
b) 196
c) 206
d) 192

Answer 1

Hint: Euclid’s division algorithm is the process of applying Euclid’s division lemma in successive times. It is given as a = bq + r, where ‘b’ is the divisor, ‘a’ is the dividend, ‘q’ is the quotient and ‘r’ is the remainder. Take a smaller number as b and greater number as ‘a’. Now, apply Euclid’s division lemma, if remainder is not 0’’ then take a = b and b = r and apply it again and again, if remainder at any stage become ’0’ then ‘b’ of that particular step is HCF i.e. divisor of that step.

Complete step-by-step answer:
We know Euclid’s division lemma static that if we divide any number by b and hence we get quotient and remainder as ‘q’ and ‘r’ respectively, then relation among them is given as
a = bq + r…………….(i)
Now, Euclid’s division algorithm works for finding HCF of two numbers by using the Euclid’s division lemma in successive manner. Steps for Euclid’s division algorithm:
1) Take the smaller number as divisor i.e. as ‘b’ and higher number as dividend i.e. as ‘a’.
2) Divide a by b and write in the form of equation a = bq + r.
3) If the remainder is not zero, then take the value of b = r and a = b. And apply the relationship again.
4) Repeat the steps (2) and (3) if the remainder at any stage becomes ‘0’ then ‘b’ of that particular step is HCF i.e. divisor of that step.
So, we can apply the given Euclid’s division approach, to find the HCF of 196 and 38220. So, let us divide 38220 by 196 as follows
\[196\overset{195}{\overline{\left){\begin{align}
  & 38220 \\
 & \underline{196} \\
 & \underline{1862} \\
 & \underline{1764} \\
 & \underline{00980} \\
 & \underline{00980} \\
 & \underline{00000} \\
\end{align}}\right.}}\]
Hence, we can write the relation with the dividend, quotient, remainder and divisor from the equation (i) as
$38220=196\times 195+0$
Now, as per the rule for finding HCF with the help of Euclid’s division algorithm, we get HCF of 196 and 38220 as 196 because remainder becomes ‘0’ at the very first step. Hence, HCF of 196 and 38220 is 196.
So, option (b) is the correct answer.

Note: Divide the number 38220 by 196 very carefully because it is the only step in the solution where students may go wrong.
Here, we get the remainder at a very early stage i.e. at the very first step. But there are problems where we need to proceed very long and have to apply many steps to get HCF. So, in all those cases, one may get confused with the values of ‘a’ and ‘b’ at each step. So, follow step 3 and carefully with those questions. Don’t confuse it with the equation a = bq + r, it is the general rule of division that the sum of remainder and products of quotient and divisor will always be equal to the dividend. So, don’t confuse the terminology with Euclid’s division.