Question

For each of the following pairs a, b of integers, find the greatest common divisor d of a and b and express d in the form ar + bs: (i) a = 7 and b = 11; (ii) a = −28 and b = −63; (iii) a = 91 and b = 126; (iv) a = 630 and b = 132; (v) a = 7245 and b = 4784; (vi) a = 6499 and b = 4288.

Answer 1

Explanation:

We are to find gcd of a and b using linear combination algorithm

a) 7 and 11. 1= 3(7)-2(11). Hence GCD =1

b) -28 and -63:

`-63 = -2(28)-7\\28=-4(7)+0`

7=-2(-28)+(-63)

So 7 is GCD

c)
`126 = 91+35\\91 = 2(35)+21\\35 = 21+14\\21 = 14+7\\14 = 2(7)`

So 7 is GCD and 7 = 7(91)-5(126)

d) 630 and 132

GCD is 6.

`630=132(4) +102\\132=102+30\\102 = 30(3)+12\\30=2(12)+6\\12=2(6)`

6=630(-9)+43(132)

e) 7245 and 4784

GCD is 23

23 = 7245(35)+4784(-53)

f) 6499 and 4288

GCD is 67

67 = 6499(-31)+4288(47)