Question

Using Euclid’s division lemma, find HDF of 693, 567 and 126.

Answer 1

Hint: Euclid’s division lemma is given as Where a is dividend, b is divisor, q is the quotient and r is the remainder of it. Rule of finding H.C.F. Euclid's division algorithm is given as that divided the higher number by the lower given in the problem and put these values in the equation mentioned above. Change a and b as b and r of the previous step, and if the remainder of any step is 0, then b of that particular step will be H.C.F.

Complete step-by-step answer:
We know Euclid’s division leave a statis that if we divide any number a by b, and hence we get quotient and remainders q and r respectively, then relation among them is given as: $a=bq+r.$
Now, Euclid’s division algorithm works for finding H.C.F. of these numbers by using the Euclid’s division lemma in successive manner. Steps for Euclid’s division algorithm:
Take the smaller number as divisor I.e. as b and higher number as dividend i.e. as a.
Divide a by b and write in form of equation $a=bq+r.$
If remainder is not zero, then take the value of b=r and a=b. And apply again.
Repeat the step (2) and (3) if remainder at any stage become zero then b of that particular step is H.C.F. i.e. divisor of that step.
So, Let us divide 693 by 567 and hence write in the form of Euclid’s division lemma I.e.
   $a=bq+r.$ So, we get
 $567\overset{1}{\overline{\left){\begin{align}
  & 693 \\
 & \underline{567} \\
 & 126 \\
\end{align}}\right.}}$
So, we get expression by Euclid’s lemma as
$693=567\times 1+126$
Now, we need to take a=567, b=126 and hence, need to divide 567 by 126. So, we get
$126\overset{4}{\overline{\left){\begin{align}
  & \text{ }567 \\
 & \underline{-504} \\
 & \text{ 6}\text{.3} \\
\end{align}}\right.}}$
So, we get expression by Euclid’s division lemma as:
$567=125\times 4+63$
Now, take a=126, b-63. So, we get
$63\overset{2}{\overline{\left){\begin{align}
  & 126 \\
 & \underline{126} \\
 & \underline{0} \\
\end{align}}\right.}}$
So, we can represent by Euclid’s division lemma as: $126=63\times 2+0$.
As the remainder becomes 0 at b=63 i.e. the given number is 63.

Note: Don’t confuse values of a and b at each step. One may go wrong here, which is the key point of the question. Don’t confuse the equation $a=bq+r.$ It is the general rule of division that sum of remainder and products of quotient and divisor will always be equal to the terminology Euclid’s division lemma.