For each x and n, find the multiplicative inverse mod n of x. your answer should be an integer s in the range 0 through n - 1. check your solution by verifying that sx mod n = 1.(a) x = 52, n = 77(b) x = 77, n = 52(c) x = 53, n = 71(d) x = 71, n = 53

Use the Euclidean algorithm to express 1 as a linear combination of and .

a. because

77 = 1*52 + 25

52 = 2*25 + 2

25 = 12*2 + 1

so we can write

1 = 25 - 12*2 = 25*25 - 12*52 = (77 - 52)(77 - 52) - 12*52 = 77^2 - 2*52*77 + 52^2 - 12*52

Taken modulo 77 leaves us with

b. First, , so really we're looking for the inverse of 25 mod 52. We've basically done the work in part (a) already:

1 = 25*25 - 12*52

Taken modulo 52, we're left with

c. The EA gives

71 = 1*53 + 18

53 = 2*18 + 17

18 = 1*17 + 1

so we get

1 = 18 - 17 = 3*18 - 53 = 3*71 - 4*53

so that taken module 71, we find

d. Same process as with (b). First we have , and we've already shown that

1 = 3*18 - 53

which means, taken modulo 53, that

answer: y=4000x+14000

step-by-step explanation: