What this calculator does
The modular inverse of a is the number that multiplies with it to give 1 modulo n. It is the modular equivalent of a reciprocal, and it exists only when a and n share no common factor.
That coprimality condition is absolute. 7 has an inverse of 15 modulo 26, since 7 times 15 is 105 which leaves remainder 1, but 13 has no inverse modulo 26 at all because the two share a factor of 13.
The formula
The extended Euclidean algorithm finds coefficients satisfying ax + ny = gcd(a, n). When the gcd is 1, reducing x modulo n gives the inverse.
| Term | Meaning |
|---|---|
| Modular inverse | The value x where a times x leaves remainder 1 modulo n. |
| Coprime | Sharing no common factor, which is the condition for an inverse to exist. |
| Extended Euclidean algorithm | The method that produces both the gcd and the inverse. |
The inputs explained
| Field | What to enter |
|---|---|
| a | The number to invert. Must be coprime to n. |
| n (modulus) | The modulus, at least 2. |
When to use it
RSA key generation
The private exponent is a modular inverse of the public one.
Solving modular equations
Dividing modulo n means multiplying by the inverse.
Affine ciphers
Decryption requires inverting the multiplier modulo the alphabet size.
Worked examples
Every figure in the tables below is produced by this page’s own calculator at build time, so the numbers and the tool always agree. Select any row to load that scenario.
What are the inverses modulo 26?
Three values coprime to 26.
| Value of a | Inverse | Check: a×inverse mod n |
|---|---|---|
| a = 3 | 9 | 1 (should equal 1) |
| a = 7 | 15 | 1 (should equal 1) |
| a = 11 | 19 | 1 (should equal 1) |
Questions
Why must a and n be coprime?
Because if they share a factor, every multiple of a shares it too, so no multiple can ever leave remainder 1. The shared factor makes reaching 1 impossible.
How many values have inverses modulo n?
Exactly as many as are coprime to n, which is Euler's totient function of n. For 26 that is 12 values out of 25, since all even numbers and 13 are excluded.
What is this used for in cryptography?
RSA fundamentally. The private key exponent is the modular inverse of the public exponent, and computing it is the step that requires knowing the prime factorisation, which is what keeps the scheme secure.
Is there a shortcut when n is prime?
Yes. When n is prime, every non-zero value has an inverse, and Fermat's little theorem gives it as a raised to the power n minus 2, modulo n. Modular exponentiation then computes it directly.
For modular exponentiation, see the modular exponentiation calculator. For simultaneous congruences, see the Chinese remainder theorem calculator.