Question

Use Euclid’s division algorithm to find the HCF of $75,243$ .

Answer 1

Hint: Here we have to find the HCF of two numbers given by using Euclid’s division algorithm. Firstly we will let the two variables equal to two numbers given in such a way that the bigger number is given the first variable name. Then we will use Euclid's division algorithm and write the bigger number in terms of the smaller number and try to make the remainder as zero by using the algorithm again and again and get our desired answer.

Complete step-by-step solution:
We have to find the HCF of $75,243$
So we will let the two numbers be equal to the variable as follows:
$a=243$
$b=75$
Now as we know according to Euclid’s division algorithm to find the HCF of two positive numbers which are $a>b$ we make the equation as $a=bq+r$ where $q=$ Quotient and $r=$ Remainder we have to make our $r=0$ and in that step whatever $b$ value will be that will be our HCF.
So we will start as follows:
Step 1: Apply division lemma to find $q$ and $r$ where $a=bq+r$ as follows:
So we divide the bigger number by the smaller number as follows:
$75\overset{3}{\overline{\left){\begin{align}
  & 243 \\
 & \underline{-225} \\
 & 18 \\
\end{align}}\right.}}$
We get $q=3$ and $r=18$ so,
$243=3\times 75+18$
As $r\ne 0$in next step we will take $a=b$ and $b=r$
Step 2: So we have $a=75$ and $b=18$ proceeding in similar manner we get,
$18\overset{4}{\overline{\left){\begin{align}
  & \,\,\,75 \\
 & -\underline{72} \\
 & \,\,\,\,\,3 \\
\end{align}}\right.}}$
So we get $q=4$ and $r=3$
$75=18\times 4+3$
Again as $r\ne 0$ in the next step we will take $a=b$ and $b=r$ .
Step 3: So we have $a=18$ and $b=3$ proceeding in similar manner we get,
$3\overset{6}{\overline{\left){\begin{align}
  & \,\,\,18 \\
 & -\underline{18} \\
 & \,\,\,\,\,0 \\
\end{align}}\right.}}$
We get $q=6$ and $r=0$ such that,
$18=3\times 6+0$
We got our $r=0$ and in this step $b=3$.
So that means our HCF is $3$
Hence Euclid's division algorithm HCF of $75,243$ is $3$ .

Note: HCF of any two or more numbers is the highest number that divides all the numbers given completely such that there is no remainder. The HCF of the numbers given is always less than or equal to the smallest number among them all. The lemma is always applied to the biggest numbers among the two numbers given as we have to divide the bigger number by smaller; the opposite is not possible to get the lemma equation.