Inverse Modulo Calculator
Enter an integer a and a modulus m to find the modular multiplicative inverse (the x such that a times x is congruent to 1 mod m) and the additive inverse (the x such that a plus x is congruent to 0 mod m). The calculator checks whether the inverse exists, applies the Extended Euclidean Algorithm, and shows every step of the working.
What is an inverse modulo?
In ordinary arithmetic, the multiplicative inverse of a number is its reciprocal: the inverse of 3 is 1/3. Modular arithmetic works differently because fractions are not defined, but the same idea still applies. The modular multiplicative inverse of an integer a with respect to modulus m is the integer x in the range 0 to m-1 such that (a * x) mod m = 1. In other words, multiplying a by x and dividing by m leaves a remainder of 1. For example, the inverse of 3 modulo 11 is 4, because 3 * 4 = 12 = 11 + 1, so 12 mod 11 = 1. The additive inverse is simpler: it is the integer x such that (a + x) mod m = 0, which is just x = (-a) mod m.
When does the multiplicative inverse exist?
The multiplicative inverse of a modulo m exists if and only if gcd(a, m) = 1, meaning a and m share no common factor other than 1 (they are coprime). If m is a prime number, then every integer from 1 to m-1 is coprime with m, so every non-zero element has a multiplicative inverse. That property makes prime moduli especially useful in cryptography and in finite fields. When m is composite, only those integers coprime with m have inverses. For example, modulo 12, the integer 4 has no multiplicative inverse because gcd(4, 12) = 4, not 1.
How the Extended Euclidean Algorithm finds the inverse
The most efficient method for computing the modular multiplicative inverse is the Extended Euclidean Algorithm. It extends the ordinary Euclidean GCD algorithm to also compute the Bezout coefficients: integers x and y such that a*x + m*y = gcd(a, m). When gcd(a, m) = 1, this equation becomes a*x + m*y = 1. Taking both sides modulo m eliminates the m*y term (since m*y is divisible by m), leaving a*x = 1 (mod m). Therefore x, normalised to the range [0, m-1], is the modular inverse. The algorithm runs in O(log min(a, m)) time, which is very efficient even for large numbers used in cryptography.
Applications in cryptography and computing
Modular multiplicative inverses appear throughout modern cryptography and computer science. In RSA encryption, the private exponent d is the modular inverse of the public exponent e modulo the totient of the key modulus - finding this inverse is a central step in key generation. In the Chinese Remainder Theorem (CRT), inverses are used to reconstruct a number from its remainders modulo several coprime integers, which is a technique for speeding up RSA decryption and other computations. In modular arithmetic over finite fields, the inverse replaces division, making it possible to perform algebra in a setting where ordinary fractions do not exist.
Modular multiplicative inverses mod 11
| a | Inverse x (a * x = 1 mod 11) | Verification |
|---|---|---|
| 1 | 1 | 1 * 1 = 1 |
| 2 | 6 | 2 * 6 = 12 = 1 mod 11 |
| 3 | 4 | 3 * 4 = 12 = 1 mod 11 |
| 4 | 3 | 4 * 3 = 12 = 1 mod 11 |
| 5 | 9 | 5 * 9 = 45 = 1 mod 11 |
| 6 | 2 | 6 * 2 = 12 = 1 mod 11 |
| 7 | 8 | 7 * 8 = 56 = 1 mod 11 |
| 8 | 7 | 8 * 7 = 56 = 1 mod 11 |
| 9 | 5 | 9 * 5 = 45 = 1 mod 11 |
| 10 | 10 | 10 * 10 = 100 = 1 mod 11 |
All non-zero integers mod 11 have a multiplicative inverse because 11 is prime. This table lists every value from 1 to 10 and its inverse.
Frequently asked questions
What is the modular multiplicative inverse?
It is the integer x in the range 0 to m-1 such that (a * x) mod m = 1. Just as dividing by a number in ordinary arithmetic is the same as multiplying by its reciprocal, multiplying by x in modular arithmetic "undoes" multiplication by a. For example, the inverse of 3 mod 11 is 4, since 3 * 4 = 12 and 12 mod 11 = 1.
Why does the multiplicative inverse sometimes not exist?
The inverse exists only when a and m are coprime, that is, gcd(a, m) = 1. If they share a common factor greater than 1, then no integer x will satisfy a*x = 1 (mod m). For example, 6 has no inverse mod 9 because gcd(6, 9) = 3. If you need inverses to always exist, choose a prime modulus, where every non-zero element is automatically coprime with the modulus.
What is the difference between the additive and multiplicative inverse?
The additive inverse of a mod m is the x such that (a + x) mod m = 0 - it "undoes" addition. It is simply (-a) mod m and always exists. The multiplicative inverse of a mod m is the x such that (a * x) mod m = 1 - it "undoes" multiplication. It only exists when gcd(a, m) = 1. For example, the additive inverse of 3 mod 11 is 8 (3 + 8 = 11 = 0 mod 11), while the multiplicative inverse of 3 mod 11 is 4 (3 * 4 = 12 = 1 mod 11).
Is the modular inverse unique?
Yes, within the standard range 0 to m-1, the modular multiplicative inverse is unique. However, there are infinitely many integers outside that range that also satisfy the congruence a*x = 1 (mod m), because adding any multiple of m to x gives another solution. The convention is to report the smallest non-negative solution, which is always in {1, ..., m-1}.
What is Fermat's Little Theorem and when can I use it?
When the modulus m is prime, Fermat's Little Theorem states that a^(m-1) = 1 (mod m) for any a not divisible by m. Rearranging gives a * a^(m-2) = 1 (mod m), so the inverse is a^(m-2) mod m. This is a simple formula but requires computing a large power, which is efficient with fast modular exponentiation. It only works for prime moduli. For composite moduli, use the Extended Euclidean Algorithm instead.
How do I verify my inverse is correct?
Multiply the original number a by the candidate inverse x and compute the product modulo m. If the result is 1, the inverse is correct. For example, to verify that 4 is the inverse of 3 mod 11, compute 3 * 4 = 12, then 12 mod 11 = 1. This calculator shows the verification step automatically for every result.