Question

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

Verified
65k+ views
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\And r$ are unique integers. We follow the same procedure until we get remainder zero.

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=\left( 1651\times 1 \right)+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=\left( 381\times 4 \right)+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=\left( 127\times 3 \right)+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=}\left( \text{Divisor}\times \text{Quotient} \right)+r\text{emainder}$