Find the multiplicative inverse of 𝑎 𝑚𝑜𝑑 𝑛 (𝑎 −1 )

Question

13(𝑚𝑜𝑑 31)

Answer 1

31(mod 13) = 5

int(31/13) = 2

31(mod 5) = 1

int(31/5) = 6

2 * 6 = 12

13^-1 = 12

As a check, 13 * 12 = 156

156 = 31 * 5 + 1