Find the modular inverse of a (mod m), perform modular arithmetic operations, and solve modular equations step by step using the Extended Euclidean Algorithm.
The modular inverse of a modulo m is the number x such that a × x ≡ 1 (mod m). It's the modular arithmetic equivalent of the reciprocal — just as 3 × (1/3) = 1 in regular arithmetic, 3 × x ≡ 1 (mod 7) has a solution x = 5 because 3 × 5 = 15 ≡ 1 (mod 7). The inverse exists if and only if GCD(a, m) = 1 — that is, a and m are coprime.
The most efficient way to find a modular inverse is the Extended Euclidean Algorithm. It extends the standard Euclidean algorithm to find integers x and y such that ax + my = GCD(a, m). When GCD(a, m) = 1, this gives ax ≡ 1 (mod m), so x is the modular inverse. The algorithm runs in O(log min(a, m)) time.
The modular inverse of a (mod m) does not exist when GCD(a, m) > 1 — that is, when a and m share a common factor greater than 1. For example, 6⁻¹ (mod 9) does not exist because GCD(6, 9) = 3 ≠ 1. The inverse always exists when m is prime and a is not a multiple of m.
RSA encryption relies on modular inverse to generate the private key. Given public exponent e and totient φ(n), the private key d is the modular inverse of e (mod φ(n)) — that is, e × d ≡ 1 (mod φ(n)). Decrypting a message encrypted with e uses d to reverse the operation, exploiting the difficulty of factoring large numbers.
When m is prime, Fermat's Little Theorem provides a fast way to find the modular inverse: a⁻¹ ≡ a^(m−2) (mod m). This works because a^(m−1) ≡ 1 (mod m) for prime m when GCD(a,m)=1, so a × a^(m−2) ≡ 1. This can be computed efficiently using fast exponentiation.
Bézout's identity states that for any integers a and b, there exist integers x and y such that ax + by = GCD(a, b). The Extended Euclidean Algorithm finds these coefficients. When GCD(a, m) = 1, this gives ax + my = 1, which means ax ≡ 1 (mod m) — so x is the modular inverse of a.