a 9 11 d 21 55 b 33 44 e 10 203 f 124 323 c 35 78 g 2002 233

a) 9, 11 d) 21, 55 b) 33, 44 e 10, 203 f) 124, 323 c) 35, 78 g 2002, 2339 h) 3457, 466910001, 13422 The extended Euclidean algorithm can be used to express gcd(a, b) as a linear combination with integer coefficients of the integers a and b. we set so 1 , sl 0, t0 = 0, and t1 = 1 and let sj Sj-2-aj-15-1 and tj = tj-2-qj_1tj-1 for 2,3,..., n, where the qj are the quotients in the di visions used when the Euclidean algorithm finds gcd(a, b

Solution

.Part(a) : Gcd(9,11)

Here any gcd x is represented in terms of linear combination as :

x=ma+nb

Now here as gcd of 9 and 11 is 1, we can write it as a linear combination as

1= 9 x 5 - 4 x 11

==================================================================================

PArt(b) : Again as gcd of 33 and 44 is 11, so in linear combination form, w e can write it as :

11 = 44x 1 - 33 x 1

====================================================================================

PArt(c) : gcd (35,78)

Its gcf is 1, so in linear combination form it is writen as :

1= 78 x 1 - 35 x 5

====================================================================================

PArt (d) : gcd (21,55)

Here gcd of 21 and 55 is again 1 that is in linear combination form is written as :

1 =21 x 21 - 55 x 8

==================================================================================

(e) gcd(101,203)

Here the GCD of 101 and 203 is also 1 that can be written in linear form as :

1= 203 x 1 - 101 x 2