Use the Euclidean algorithm to express 1 as a linear combination of [tex]x[/tex] and [tex]n[/tex].
a. [tex]52^{-1}\equiv40\pmod{77}[/tex] 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
[tex]1\equiv52\cdot52-12\cdot52\equiv40\cdot52\pmod{77}\implies52^{-1}\equiv40\pmod{77}[/tex]
b. First, [tex]77\equiv25\pmod{52}[/tex], 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
[tex]1\equiv25\cdot25\pmod{52}\implies25^{-1}\equiv25\pmod{52}[/tex]
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
[tex]1\equiv(-4)\cdot53\pmod{71}\implies53^{-1}\equiv-4\equiv67\pmod{71}[/tex]
d. Same process as with (b). First we have [tex]71\equiv18\pmod{53}[/tex], and we've already shown that
1 = 3*18 - 53
which means, taken modulo 53, that
[tex]1\equiv3\cdot18\pmod{53}\implies71^{-1}\equiv18^{-1}\equiv3\pmod{53}[/tex]
