Question

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

Answer 1

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

a. $52^{-1}\equiv40\pmod{77}$ 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

$1\equiv52\cdot52-12\cdot52\equiv40\cdot52\pmod{77}\implies52^{-1}\equiv40\pmod{77}$

b. First, $77\equiv25\pmod{52}$, 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

$1\equiv25\cdot25\pmod{52}\implies25^{-1}\equiv25\pmod{52}$

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

$1\equiv(-4)\cdot53\pmod{71}\implies53^{-1}\equiv-4\equiv67\pmod{71}$

d. Same process as with (b). First we have $71\equiv18\pmod{53}$, and we've already shown that

1 = 3*18 - 53

which means, taken modulo 53, that

$1\equiv3\cdot18\pmod{53}\implies71^{-1}\equiv18^{-1}\equiv3\pmod{53}$