Find the modular multiplicative inverse a⁻¹ mod m using the extended Euclidean algorithm.
The modular multiplicative inverse of a modulo m is an integer x such that a × x ≡ 1 (mod m). It exists if and only if gcd(a, m) = 1 (a and m are coprime). The extended Euclidean algorithm finds Bézout coefficients x, y with a×x + m×y = 1, and x mod m is the inverse.
Modular inverse
a × a⁻¹ ≡ 1 (mod m), exists iff gcd(a, m) = 1
The inverse of a mod m does not exist when a and m share a common factor greater than 1, i.e. gcd(a, m) ≠ 1. For example, 4 has no inverse mod 6 because gcd(4, 6) = 2.
It is essential in RSA encryption, solving linear congruences, the Chinese Remainder Theorem, and modular division. In RSA, the private key is essentially a modular inverse of the public exponent.