Multiplicative Inverse Modulo Calculator

What Is the Multiplicative Inverse Modulo?

The multiplicative inverse modulo calculator finds the unique integer x that satisfies the congruence a · x ≡ 1 (mod m), where a is any integer and m is the chosen modulus. This value, written a^-1 mod m, is the modular analogue of an arithmetic reciprocal: multiplying a by its inverse always yields a remainder of 1 when divided by m. The result is always the unique integer in the range [0, m − 1].

Existence Condition

An inverse exists if and only if gcd(a, m) = 1. When a and m share a common factor greater than 1, no integer x can satisfy the congruence, and the calculator returns −1. For example, gcd(4, 6) = 2 ≠ 1, so 4 has no inverse modulo 6. When m is prime, every nonzero residue from 1 to m − 1 is guaranteed to have an inverse, which is why prime moduli dominate cryptographic design.

The Extended Euclidean Algorithm

The most efficient method for computing a modular inverse is the Extended Euclidean Algorithm. It generalizes the classical Euclidean algorithm to express gcd(a, m) as an integer linear combination:

gcd(a, m) = a · s + m · t

When gcd(a, m) = 1, the coefficient s satisfies a · s ≡ 1 (mod m). Reducing s into the range [0, m − 1] yields the inverse. According to Wichita State University's Discrete Mathematics reference on multiplicative inverses, this algorithm runs in O(log min(a, m)) steps, making it practical even for very large integers used in cryptography. The University of Washington CSE 311 course notes on Bézout's Theorem formally prove that such coefficients always exist and are computable by back-substitution through the Euclidean remainder chain.

Worked Example 1: 3^-1 mod 7

• Euclidean step: 7 = 2 · 3 + 1
• Back-substitute: 1 = 7 − 2 · 3
• So 3 · (−2) ≡ 1 (mod 7)
• Reduce: −2 mod 7 = 5, giving 3^-1 mod 7 = 5
• Verify: 3 × 5 = 15, and 15 mod 7 = 1 ✓

Worked Example 2: 7^-1 mod 11

• Euclidean chain: 11 = 1 · 7 + 4; 7 = 1 · 4 + 3; 4 = 1 · 3 + 1
• Back-substitute: 1 = 4 − 3 = 4 − (7 − 4) = 2 · 4 − 7 = 2(11 − 7) − 7 = 2 · 11 − 3 · 7
• So 7 · (−3) ≡ 1 (mod 11)
• Reduce: −3 mod 11 = 8, giving 7^-1 mod 11 = 8
• Verify: 7 × 8 = 56, and 56 mod 11 = 1 ✓

Variables Explained

• Integer a: The number whose modular inverse is sought. Accepts any integer; negative values are automatically reduced modulo m before processing. The inverse exists only when gcd(a, m) = 1.
• Modulus m: Must be an integer ≥ 2. Prime values of m guarantee that every nonzero element in [1, m − 1] has an inverse. Composite moduli may leave some residues without inverses.

Uniqueness of the Result

When it exists, the inverse is unique within [0, m − 1]. If both x and y satisfy a · x ≡ a · y ≡ 1 (mod m), subtraction gives a · (x − y) ≡ 0 (mod m). Because gcd(a, m) = 1, it follows that x ≡ y (mod m), confirming exactly one canonical representative exists in the specified range.

Practical Applications

• RSA Cryptography: The private exponent d satisfies e · d ≡ 1 (mod φ(n)), computed as a modular inverse of the public exponent e.
• Chinese Remainder Theorem: Reconstructing solutions to simultaneous congruences requires inverses of partial moduli, as detailed in Carnegie Mellon's Math 127 notes on the Chinese Remainder Theorem.
• Competitive Programming: Modular division of a value by k equals multiplication by k^-1 mod p, commonly applied with the prime modulus 10⁹ + 7 to keep intermediate results bounded.
• Elliptic Curve Cryptography: Point doubling and addition on finite-field elliptic curves require modular inverses for coordinate arithmetic.