Question

Using the method followed in Example 17, express the greatest common divisor of each of these pairs of integers as a linear combination of these integers. a) 9, 11 b) 33, 44 c) 35, 78 d) 21, 55 e) 101, 203 f ) 124, 323 g) 2002, 2339 h) 3457, 4669 i) 10001, 13422

Answer 1

Answer:

a) 1= 5*9 -4*11

b) 3 * 33 - 2 * 44 = 11

c)  29*35-13*78 = 1

d) 21*21 - 8 * 55 = 1

e) 1 * 203 - 2*101 = 1

f) 43*323-112*124 = 1

g) 701*339-819*2002 = 1

h) 1252* 3457 - 927 * 4669 = 1

i) 1793*10001 - 1336 * 13422 = 1

Step-by-step explanation:

a)

11-9 = 2

9 - 4*2 = 1

Now, we replace 2

1 = 9-4*(11-9) = -4*11 +5*9

b) 44-33 = 11

33- 2*11 = 11 (we cant reduce anymore because we reach 11 again)

we replace 11

11 = 33 - 2 ( 44-33) = 3 * 33 - 2 * 44

78-35 = 43

78-2*35 = 43-35 = 8

35-4*8 = 3

8-2*3 = 2

3-2 = 1

Now, we replace

1 = 3-2 = 3 - (8-2*3) = - 8 + 3*3 = - 8 + 3 * (35-4*8) = 3 * 35 -13*8 = 3 * 35 - 13*(78-2*35 ) = 29*35 - 13 * 78

d)

55-2*21= 13

21-13 = 8

13-8 = 5

8-5 = 3

5-3 = 2

3-2 = 1

1 = 3- (5-3) = (8-5) - (5- (8-5) ) = 2 * 8 - 3 * 5 = 2*8 - 3* (13-8) = 5*8 - 3*13 = 5*(21-13) -3*13 = 5*21 - 8*13 = 5*21 - 8 *(55-2*21) = 21*21 -8*55

e) 1* 203-2*101 = 1

f) 323-2*124 = 75

124-75 = 49

75-49 = 26

49-26 = 23

26-23 = 3

23-7*3 = 2

3-2 = 1

1 = 3-2 = 3 - (23-3*7) = 8*3 - 23 = 8 *(26-23) - 23 = 8*26-9*23 = 8*26-9*(49-26) = 17*26 - 9*49 = 17*(75-49)-9*49 = 17*75- 26*49 = 17*75 - 26*(124-75) = 43*75 -26*124 = 43*(323-2*124)-26*124 = 43*323 - 112*124

g)

2339 - 2002 = 337

2002 - 337*5 = 317

337-317 = 20

317-15*20 = 17

20-17 = 3

17-5*3 = 2

3-2 = 1

1 = 3-2 = 3- (17-5*3) = 6*3-17 = 6*(20-17)-17 = 6*20-7*17 = 6*20 - 7*(317-15*20) = 111*20 - 7*317 = 111*(337-317) - 7*317 = 111*337 - 118*317 = 111*337 - 118*(2002-5*337) = 701*337 - 118*2002 = 701*(2339-2002)-118*2002 = 701*2339 - 819*2002.

h) 4669-3457 = 1212

3457- 2* 1212 = 1033

1212 - 1033 = 179

1033 - 5*179 = 138

179-138 = 41

138-3*41 = 15

41-2*15 = 11

15-11 = 4

11-4*2 = 3

4-3 = 1

1 = 4-3 = 4-(11 - 2 *4) = 3 * 4 - 11 = 3 * (15-11) - 11 = 3 * 15 - 4*11 = 3 * 15 - 4 *(41-2*15) = 11*15 - 4*41 = 11* (138-3*41) - 4*41 = 11*138 -37*41 = 11*138-37*(179-138) = 48*138-37*179 = 48*(1033-5*179) - 37*179 = 48*1033 - 277 *179 = 48*1033 - 277 * (1212 - 1033) = 325 * 1033 -277 * 1212 = 325* (3457 - 2* 1212) - 277*1212 = 325* 3457 - 927* 1212 = 325 * 3457 - 927 *(4669- 3457) = 1252* 3457 - 927 * 4669

h) 13422-10001 = 3421

10001 - 2*3421 = 3159

3421-3159 = 262

3159-12*262 = 15

262-17*15 = 7

15-2*7 = 1

1 = 15-2*7 = 15- 2* (262-17* 15) = 35*15 - 2*262 = 35* (3159-12*262) -2*262 = 35*3159 - 422*262 = 35*3159 - 422*(3421-3159) = 457 * 3159 - 422*3421 = 457 * (10001-2*3421) - 422*3421 = 457*10001 - 1336*3421 = 457*10001 - 1336*(13422-10001) = 1793*10001 - 1336 * 13422