Modular Inverse Calculator

Find the modular inverse a⁻¹ mod m using the Extended Euclidean Algorithm. Shows Bézout coefficients, existence check, Fermat's Little Theorem method for prime moduli, and RSA application.

a⁻¹ mod m
—
Verify: a × a⁻¹ mod m —
gcd(a, m) —
Extended More scenarios, charts & detailed breakdown ▾
a⁻¹ mod m
—
Bézout: x·a + y·m = 1 —
Verification —
Professional Full parameters & maximum detail ▾

Algorithms

Inverse via Extended Euclidean —
Inverse via Fermat's Little Theorem —
Bézout Coefficients (x, y) —

Analysis

Complexity —
RSA Application —

How to Use This Calculator

  1. Enter a and m. The inverse a⁻¹ mod m is shown instantly.
  2. Use Verify Existence tab to check if an inverse is possible.
  3. Use Multiple a Values to test 3 candidates against one modulus.
  4. Use Professional to compare Extended Euclidean vs Fermat's Little Theorem.

Formula

a × a⁻¹ ≡ 1 (mod m)

Extended Euclidean: find x, y with a·x + m·y = gcd(a,m). If gcd=1, then x mod m is the inverse.

Example

3⁻¹ mod 7: Extended GCD gives 3×5 + 7×(−2) = 1, so inverse = 5. Check: 3×5=15 ≡ 1 (mod 7). ✓

Frequently Asked Questions

  • The modular inverse of a modulo m is a number x such that a × x ≡ 1 (mod m) — meaning (a × x) leaves a remainder of 1 when divided by m. It is the modular analogue of the reciprocal: just as 3 × (1/3) = 1 in ordinary arithmetic, in modular arithmetic 3 × 5 = 15 ≡ 1 (mod 7), so 5 is the modular inverse of 3 mod 7. The inverse exists if and only if gcd(a, m) = 1. For example, 3⁻¹ mod 7 = 5, but 4⁻¹ mod 6 does not exist because gcd(4,6) = 2 ≠ 1.
  • The most general method is the Extended Euclidean Algorithm. It finds integers x and y satisfying Bezout's identity: a·x + m·y = gcd(a, m). When gcd = 1, this gives a·x ≡ 1 (mod m), so x mod m is the inverse. Example: find 3⁻¹ mod 7. Extended GCD on (3, 7): 7 = 2×3 + 1 → 1 = 7 − 2×3 → 3×(−2) + 7×1 = 1 → x = −2 ≡ 5 (mod 7). Verify: 3 × 5 = 15 = 7×2 + 1 ≡ 1 (mod 7). ✓
  • A modular inverse of a modulo m does not exist when gcd(a, m) ≠ 1 — that is, when a and m share a common factor greater than 1. For example, 4⁻¹ mod 6 does not exist because gcd(4, 6) = 2. Intuitively: 4x is always even, so 4x mod 6 can only be 0, 2, or 4 — it can never equal 1. The condition gcd(a, m) = 1 (coprimality) is both necessary and sufficient for the inverse to exist. Entering such a pair in this calculator returns "No inverse exists."
  • When the modulus m = p is a prime number and gcd(a, p) = 1, Fermat's Little Theorem provides a shortcut: a⁻¹ ≡ a^(p−2) mod p. This avoids the Extended Euclidean Algorithm by computing a single modular exponentiation. Example: 3⁻¹ mod 7 = 3^(7−2) mod 7 = 3^5 mod 7 = 243 mod 7 = 5. Verify: 3 × 5 = 15 ≡ 1 (mod 7). ✓ This method is simpler to implement but only works for prime moduli. For composite moduli, use the Extended Euclidean Algorithm.
  • Modular inverses appear throughout cryptography and computer science. In RSA encryption, the private key d is computed as d = e⁻¹ mod φ(n), where φ(n) is Euler's totient and e is the public exponent. In the Chinese Remainder Theorem, inverses are needed to combine congruences. In Diffie-Hellman key exchange and elliptic curve cryptography, inversions occur in group operations. Modular inverses also appear in error-correcting codes, secret sharing schemes (Shamir's Secret Sharing), and algorithm design (e.g., computing modular division).

Related Calculators

φ Euler Totient φ(n) gcd+ Extended Euclidean 🔐 RSA Key Calculator mod Chinese Remainder Theorem
Sources & References (5) ▾
  1. An Introduction to the Theory of Numbers — Hardy & Wright — Oxford University Press
  2. Concrete Mathematics — Graham, Knuth & Patashnik — Addison-Wesley
  3. Modular Multiplicative Inverse — Wolfram MathWorld — Wolfram Research
  4. Khan Academy — Modular Inverses — Khan Academy
  5. NIST DLMF — §27.4 Euler's Criterion — NIST