Question

Use Euclid’s algorithm to find HCF of $1651$ and $2032$ . Express the HCF in the form $1651m+2032n$.

Answer 1

Hint: First we recall Euclid's algorithm; we can calculate the HCF of two integers by using Euclid’s division algorithm. First assume the greater number as $a$ and smaller number as $b$ . Now, express the numbers in the form of $a=bq+r$ where, $q\mathrm{\&}r$ are unique integers. We follow the same procedure until we get remainder zero.

Complete step-by-step answer:
We have given that numbers $1651$ and $2032$ .
We have to find the HCF by using Euclid’s algorithm.
Now, we compare both numbers, we get
 $2032>1651$
Let us assume $1651=b$ and $2032=a$ .
Now, expressing the numbers in the form $a=bq+r$ , we get
 $2032=(1651\times 1)+381$
As $381\ne 0$, we repeat the same process with $1651$ and $381$.
Now, assume $1651=a$ and $381=b$.
Now, expressing the numbers in the form $a=bq+r$ , we get
 $1651=(381\times 4)+127$
As $127\ne 0$ , we repeat the same process with $381$ and $127$ .
Now, assume $381=a$ and $127=b$ .
Now, expressing the numbers in the form $a=bq+r$ , we get
 $381=(127\times 3)+0$
Since the remainder is zero, we can not proceed further.
The HCF of $1651$ and $2032$ is $127$.

Note: The basis of Euclid’s algorithm is Euclid’s division Lemma. The word Lemma is already a proven statement used to prove other statements. On the other hand, an algorithm is a set of steps used to solve a problem. Euclid’s division lemma is used to prove other theorems. Euclid’s division algorithm is follows the form:
$\text{Dividend=}(\text{Divisor}\times \text{Quotient})+r\text{emainder}$