Find \(24^{-1} \pmod{11^2}\). That is, find \(b\) the residue for which \(24b \equiv 1\pmod{11^2}\).
Express your answer as an integer from \(0\) to \(11^2-1\), inclusive.
The modular inverse of 24 mod 121 is 96. This can be found using the Extended Euclidean Algorithm.
def extended_euclidean_algorithm(a, b): if b == 0: return (a, 1, 0) else: q, r = divmod(a, b) x, y, z = extended_euclidean_algorithm(b, r) return (z, y - q * z, x) def modular_inverse(a, m): g, x, y = extended_euclidean_algorithm(a, m) if g != 1: raise ValueError("No modular inverse exists") else: return x % m print(modular_inverse(24, 121))
This prints:
96
So the answer is 96.
