Question

Using Euclid's algorithm, find the HCF of 1651 and 2032. Express

the HCF in the form (1651m + 2032n) for some integers m and n.

Answer 1

Since 2032 gt 1651, we divide 2032 by 1651 to get 1 as quotient and 381 as remainder. step 2. Since the remainder 381≠0 , we divide 1651 by 381 to get 4 as quotient and 127 as remainder.

Explanation:

Euclid algorithm lemma, a = bq + r where 0 ≤ r < b

From Euclid algorithm lemma, 2032 = 1651 × 1 + 381

Using lemma for 1651 and 381, e.g., 1651 = 381 × 4 + 127

Similarly, use lemma for 381 and 127, e.g., 381 = 127 × 3 + 0

Hence, HCF = 127

Now, 127 = 1651M + 2032 N

⇒127 = (127 × 13)M + (127 × 16)M

⇒1 = 13M + 16 N

Here many solutions possible because we have one equation contains two variable.

Assume M = 5 and N = -4

Then, 13 × 5 + 16 × -4 = 65 – 64 = 1

So, HCF of 1651 and 2032 in the form of 1651M + 2032 N is [1651(5) + 2032(-4)]