How to Find a Modular Inverse
The modular multiplicative inverse of an integer a with respect to a modulus m is the integer x, with 0 ≤ x < m, that satisfies a · x ≡ 1 (mod m). It behaves like the reciprocal 1/a from ordinary arithmetic, letting you "divide by a" inside modular arithmetic, where standard division is not defined. This calculator finds that value using the extended Euclidean algorithm and confirms whether an inverse exists at all.
The extended Euclidean algorithm
The ordinary Euclidean algorithm finds gcd(a, m) by repeated division with remainder. The extended version tracks two running coefficient sequences alongside each step so that, once the algorithm terminates, it has produced integers x and y satisfying Bézout's identity: a·x + m·y = gcd(a, m). When gcd(a, m) = 1, this equation becomes a·x + m·y = 1, which means a·x ≡ 1 (mod m) — so x, reduced into the range [0, m-1] by adding multiples of m if needed, is exactly the modular inverse. This calculator runs that algorithm on your two inputs and reports gcd(a, m), the inverse x, and a verification that (a × x) mod m = 1.
When no inverse exists
An inverse exists if and only if a and m are coprime, i.e. gcd(a, m) = 1. If a and m share a common factor greater than 1, no integer x can satisfy a·x ≡ 1 (mod m), and the calculator reports the gcd instead so you can see why. For example, 6 has no inverse mod 9 because gcd(6, 9) = 3 ≠ 1. Note that the inverse depends only on a mod m, so negative or oversized values of a are first reduced into the range [0, m-1] before the algorithm runs.
Real-world applications
- Cryptography: RSA key generation and decryption depend on computing a modular inverse of the public exponent modulo Euler's totient of the key.
- Affine and classical ciphers: decrypting an affine cipher requires the modular inverse of the multiplicative key (e.g. 7⁻¹ mod 26 = 15 for a 26-letter alphabet).
- Modular division and solving linear congruences: solving a·x ≡ b (mod m) is done by multiplying both sides by the modular inverse of a.
- Hashing and error-correcting codes: several checksum and coding schemes rely on modular inverses to reverse a modular multiplication step.