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.
How we build and check this calculator
This calculator runs entirely in your browser, so the numbers you enter stay on your device. The math behind it is written by hand and tested against worked examples and standard references before the page goes live.
SuperGlobalCalculator is independently built and maintained. See how we build and verify our calculators.