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\And 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=\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} $