Modular Multiplicative Inverse Calculator

What Is the Modular Multiplicative Inverse?

The modular multiplicative inverse of an integer a with respect to modulus m is an integer x in the range [0, m-1] such that:

It is written as a⁻¹ (mod m) and is analogous to the multiplicative inverse in ordinary arithmetic (i.e., 1/a), but in the world of modular arithmetic.

Key condition: The inverse exists if and only if gcd(a, m) = 1 — that is, a and m must be coprime.

How It Is Calculated: Extended Euclidean Algorithm

The most efficient method uses the Extended Euclidean Algorithm. It finds integers x and y satisfying Bézout's identity:

When gcd(a, m) = 1, taking both sides mod m gives a·x ≡ 1 (mod m), so x is the modular inverse.

Example: Find 3⁻¹ (mod 7):

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

Applications in Cryptography & Mathematics

Frequently Asked Questions