Modular Inverse Calculator
Find the modular multiplicative inverse of a mod m with the extended Euclidean algorithm: every division step, the Bézout identity, a check, and when no inverse exists.
How it works
a·x ≡ 1 (mod m) has a solution iff gcd(a, m) = 1 · extended Euclid finds s, t with m·s + a·t = 1, so a⁻¹ ≡ t (mod m)
The modular inverse of a modulo m is the number x between 0 and m − 1 with a·x ≡ 1 (mod m). It exists exactly when a and m share no common factor. The extended Euclidean algorithm runs the ordinary Euclidean algorithm for gcd(m, a) while tracking coefficients, ending with Bézout’s identity m·s + a·t = 1; reducing t modulo m gives the inverse. It is the basis of RSA key generation and of solving linear congruences.
Worked example
For 3 mod 11: 11 = 3 × 3 + 2, 3 = 1 × 2 + 1, 2 = 2 × 1 + 0. Back-substituting gives 11·(−1) + 3·4 = 1, so the inverse is 4. Check: 3 × 4 = 12 ≡ 1 (mod 11).
Sources: Modular multiplicative inverse — Wikipedia · Extended Euclidean algorithm — Wikipedia
Frequently asked questions
When does a modular inverse not exist?
When gcd(a, m) > 1. For example 4 has no inverse mod 10 because both are even, so 4x is always even and can never be 1 more than a multiple of 10.
Can I use Fermat’s little theorem instead?
If m is prime, a⁻¹ ≡ a^(m−2) (mod m). For 3 mod 11 that is 3⁹ = 19,683 ≡ 4 (mod 11). The extended Euclidean algorithm works for any coprime a and m.
What about negative a?
The calculator first reduces a into the range 0 to m − 1 (for example −3 mod 11 = 8) and then finds the inverse of that.
Where is the modular inverse used?
In RSA (the private exponent d is the inverse of e modulo φ(n)), in the Chinese remainder theorem, in hashing and in solving linear congruences a·x ≡ b (mod m).
Related calculators
This calculator is for educational purposes. Double-check important results before acting on them.