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

We find HCF (n 1651 , 2032) using the following steps.

Step1. Since 2032 gt 1651, we divide 2032 by 1651 to get 1 as quotient and 381 as remainder.

by Eulid's divison lemma,

we get

2032=1651×1+381

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

by Euclid's divison lemma, we get

1651=381×4+127

Step3. since the remainder 127≠0 , we divide 381 by 127 to get 3 as quotient and 0 as remainder.

by Euclid's divison lemma, we get

381=127×3+0

the remainder is now 0, so our proceduce stops.

HCF ( 1651 , 2032) = 127

Now from (ii) , we get

1651=381×4+127

⇒127=1651−381×4

⇒127=1651−(2032−1651×1)×4

⇒127=1651−2032×4+1651×4

⇒127=1651×5+2032×(−4)

Hence , m =5 n=-4