About the Modular Inverse Calculator
This modular inverse calculator finds the modular multiplicative inverse of a number a modulo m — the value x between 0 and m − 1 for which a·x leaves a remainder of 1 when divided by m. It runs the extended Euclidean algorithm, shows every division step with its quotient, remainder and the running coefficients, and reports the Bézout identity a·s + m·t = gcd(a, m) that the inverse comes from.
It is useful for number theory and discrete mathematics courses, for cryptography work such as computing an RSA private exponent d = e⁻¹ mod φ(n), for solving linear congruences a·x ≡ b (mod m), and for programming tasks that need division in modular arithmetic. Inputs can be very large — hundreds of digits — because all arithmetic is exact.
An inverse exists only when a and m are coprime (gcd(a, m) = 1). If they share a factor, the calculator tells you the gcd and explains why no inverse exists. Negative values of a are reduced modulo m first.
How to use the modular inverse calculator
- 1Enter the number a you want to invert.
- 2Enter the modulus m (2 or more).
- 3Read the inverse and the check a × a⁻¹ ≡ 1 (mod m).
- 4Follow the table to see each step of the extended Euclidean algorithm.
Formula and method
The extended Euclidean algorithm repeatedly divides: rₖ₊₁ = rₖ₋₁ − qₖ·rₖ, starting from r₀ = m and r₁ = a, until the remainder is 0. Alongside each remainder it tracks coefficients s and t with rₖ = s·m + t·a, updated by the same rule (sₖ₊₁ = sₖ₋₁ − qₖ·sₖ, likewise for t). The last non-zero remainder is gcd(a, m), and its coefficients give Bézout’s identity a·t + m·s = gcd(a, m).
If the gcd is 1, reducing that equation modulo m gives a·t ≡ 1, so t (shifted into the range 0 … m − 1) is the modular inverse. If the gcd is greater than 1, no inverse exists. The algorithm takes O(log m) steps, so it is fast even for numbers with hundreds of digits.
- a
- Number to invert
- m
- Modulus
- q, r
- Quotient and remainder at each division
- s, t
- Running Bézout coefficients of m and a
Worked examples
RSA textbook example: 17⁻¹ mod 3120
With p = 61, q = 53 and φ(n) = 3120, the public exponent e = 17 needs d = 17⁻¹ mod 3120. The algorithm gives 17·(−367) + 3120·2 = 1, and −367 + 3120 = 2753. Check: 17 × 2753 = 46,801 = 15 × 3120 + 1.
3⁻¹ mod 11
11 = 3·3 + 2, 3 = 1·2 + 1, so working backwards 1 = 3 − 2 = 3 − (11 − 3·3) = 4·3 − 11. The inverse is 4, since 3 × 4 = 12 = 11 + 1.
No inverse: 6 mod 15
gcd(6, 15) = 3, so every multiple of 6 leaves a remainder of 0, 3, 6, 9 or 12 when divided by 15 — never 1. A modular inverse only exists when the numbers are coprime.
Negative input: −7 mod 26
−7 ≡ 19 (mod 26). Since 19 × 11 = 209 = 8 × 26 + 1, the inverse of −7 modulo 26 is 11 (useful in affine ciphers over the 26-letter alphabet).
Frequently asked questions
What is a modular inverse?+
The modular inverse of a modulo m is a number x such that a·x ≡ 1 (mod m) — multiplying by x undoes multiplying by a in arithmetic mod m. For example 3 × 4 = 12 ≡ 1 (mod 11), so 4 is the inverse of 3 mod 11.
When does a modular inverse exist?+
Exactly when gcd(a, m) = 1, i.e. a and m are coprime. If m is prime, every a that is not a multiple of m has an inverse. If they share a factor, no inverse exists.
How does the extended Euclidean algorithm find the inverse?+
It runs Euclid’s gcd algorithm while keeping track of how each remainder is written as s·m + t·a. When the remainder reaches 1, the equation a·t + m·s = 1 shows that t is the inverse modulo m.
Can I use Fermat’s little theorem instead?+
Yes, when m is prime: a⁻¹ ≡ a^(m−2) (mod m). For example 3⁹ mod 11 = 4. Euler’s theorem generalises this to a^(φ(m)−1) for coprime a and m, but the extended Euclidean algorithm works for any m without knowing φ(m).
How is the modular inverse used in RSA?+
The private exponent d is the inverse of the public exponent e modulo φ(n) (or λ(n)). With e = 17 and φ(n) = 3120, d = 2753, because 17 × 2753 ≡ 1 (mod 3120).
How do I solve a linear congruence a·x ≡ b (mod m)?+
If gcd(a, m) = 1, multiply both sides by a⁻¹: x ≡ a⁻¹·b (mod m). For 3x ≡ 5 (mod 11), x ≡ 4 × 5 = 20 ≡ 9 (mod 11).