Modular Inverse Calculator
Find the modular multiplicative inverse a⁻¹ mod m using the extended Euclidean algorithm.
Used in cryptography, RSA, and number theory.
Modular Inverse
The modular inverse of an integer a modulo m is the integer x such that
a × x ≡ 1 (mod m)
It is the multiplicative analogue of an additive negative — instead of “what number cancels a by addition” we ask “what number cancels a by multiplication, mod m.”
Existence Condition
The inverse a⁻¹ mod m exists if and only if gcd(a, m) = 1 — that is, a and m are coprime. If they share a common factor, no integer x can satisfy a × x ≡ 1 (mod m).
Worked Example — 3⁻¹ mod 11
Try values 1, 2, 3, …
- 3 × 4 = 12 = 11 + 1 ≡ 1 (mod 11) ✓
So 3⁻¹ ≡ 4 (mod 11). Check: 3 × 4 = 12, and 12 mod 11 = 1.
Algorithm — Extended Euclidean
The brute-force approach above is slow for large m. The extended Euclidean algorithm finds integers x, y such that:
a × x + m × y = gcd(a, m)
When gcd = 1, the value x mod m is the modular inverse. This runs in O(log m) operations, which is what makes RSA, elliptic-curve cryptography, and modular exponentiation tractable on real keys.
Why It Matters
| Use | Modular Inverse Role |
|---|---|
| RSA decryption | Private key d = e⁻¹ mod φ(n) |
| Elliptic-curve crypto | Point doubling and addition formulas |
| CRT (Chinese Remainder Theorem) | Combining residues |
| Hashing | Some uniform-hash families need inverses mod p |
| Linear Diophantine equations | Solving ax + by = c |
Common Mod Values
| m | Coprime to | Notes |
|---|---|---|
| Prime p | Every 1 ≤ a < p | Inverse always exists |
| 12 | 1, 5, 7, 11 | Other a have no inverse |
| 2ᵏ | All odd a | Used in fast modular code |
| RSA modulus | (p−1)(q−1)-coprime values | Drives the secret key |
Caveats
The result returned is the canonical representative in [0, m). Any value congruent to it modulo m is also a valid inverse — for example, 4 and 15 are both inverses of 3 mod 11, since 15 = 4 + 11. By convention, calculators and crypto libraries return the smallest non-negative value.