Inverse Modulo Calculator

The inverse modulo m of a number a is the integer x between 0 and m − 1 for which a·x leaves a remainder of 1 when divided by m. It is written a⁻¹ mod m and is also called the modular multiplicative inverse.

In ordinary arithmetic the inverse of 5 is 1/5, because 5 × 1/5 = 1. Modular arithmetic only has whole numbers, so "dividing by a" has to be replaced by "multiplying by a⁻¹". For example, 3 × 5 = 15 = 2·7 + 1, so 3⁻¹ ≡ 5 (mod 7).

Key facts about the modular inverse:

1. Existence: a⁻¹ mod m exists exactly when gcd(a, m) = 1.
2. Uniqueness: when it exists, there is only one inverse in the range 0 to m − 1; all others differ by multiples of m.
3. Symmetry: if x is the inverse of a, then a is the inverse of x.
4. Self-inverse values: 1 and m − 1 are always their own inverses, since (m − 1)² = m² − 2m + 1 ≡ 1.

To find a⁻¹ mod m, run the Euclidean algorithm on m and a, then work backwards to write 1 as s·m + t·a; the coefficient t, reduced mod m, is the inverse.

1. Divide repeatedly. Write m = q₁·a + r₁, then a = q₂·r₁ + r₂, and continue until the remainder is 0.
2. Check the last non-zero remainder. That is gcd(a, m). If it is not 1, stop: no inverse exists.
3. Track coefficients. Alongside each remainder keep t with the update t_new = t_old − q·t, starting from 0 and 1.
4. Read the answer. When the remainder reaches 1, the t on that row satisfies t·a ≡ 1 (mod m). Add m if t is negative.

The method needs at most about 2.08·ln(m) + 1.67 division steps (Lamé's theorem), which is why it finds inverses of 300-digit RSA numbers instantly.

A modular inverse of a exists if and only if a and m are coprime, meaning gcd(a, m) = 1. Bézout's identity guarantees integers s and t with s·m + t·a = gcd(a, m). When the gcd is 1, reducing that equation mod m leaves t·a ≡ 1, so t is the inverse.

If the gcd is some d > 1, every product a·x is a multiple of d, and so is every value it can reduce to mod m. The number 1 is never a multiple of d, so no inverse can exist.

• Prime modulus: every a from 1 to p − 1 has an inverse, which is why finite fields use prime moduli.
• Composite modulus: only the φ(m) numbers coprime to m are invertible. For m = 26, that is 12 of the 25 non-zero letters, which limits the keys of an affine cipher.

When m is prime, the inverse can also be computed as a^m−2 mod m. Fermat's little theorem says a^p−1 ≡ 1 (mod p) for a prime p not dividing a, so a · a^p−2 ≡ 1.

Euler's theorem generalises this to any modulus: a^φ(m) ≡ 1 (mod m) when gcd(a, m) = 1, so a⁻¹ ≡ a^φ(m)−1 (mod m). The catch is that you need φ(m), which requires factoring m.

The power is evaluated with square-and-multiply: write the exponent in binary, square at every bit, and multiply by a whenever the bit is 1. This takes about log₂(m) multiplications, the same order of work as the extended Euclidean algorithm, and it is the method used inside many cryptographic libraries for prime fields.

RSA's private key is a modular inverse: d = e⁻¹ mod φ(n). Choose two primes p and q, set n = p·q and φ(n) = (p − 1)(q − 1), and pick a public exponent e coprime to φ(n). The private exponent d is the inverse of e modulo φ(n).

Encryption computes c = M^e mod n and decryption computes M = c^d mod n. Because e·d = 1 + k·φ(n), Euler's theorem makes the two exponents cancel and returns the original message.

Modular inverses appear across cryptography and computing:

• Affine and Hill ciphers decrypt by multiplying with the inverse key mod 26.
• Elliptic-curve cryptography divides by a coordinate difference in every point addition, which is a modular inverse.
• The Chinese remainder theorem combines residues using inverses of the moduli.
• Competitive programming computes n choose k mod 10⁹ + 7 with inverse factorials.