Calculate Modular Inverse Instantly
Enter an integer a and a modulus m. The calculator finds a⁻¹ mod m when it exists.
Tip: Negative values for a are allowed. The calculator reduces them automatically modulo m.
What is a multiplicative inverse modulo?
A multiplicative inverse modulo m is a number that “undoes” multiplication under modular arithmetic. For an integer a, its inverse is a value x such that:
a × x ≡ 1 (mod m)
If such an x exists, then a is said to be invertible modulo m. This idea is central in number theory and practical cryptography.
When does the inverse exist?
The inverse exists if and only if the greatest common divisor of a and m is 1:
gcd(a, m) = 1
- If gcd(a, m) = 1, inverse exists and is unique modulo m.
- If gcd(a, m) > 1, no multiplicative inverse exists.
How this calculator works
Extended Euclidean Algorithm
This calculator uses the Extended Euclidean Algorithm to solve: a·x + m·y = gcd(a, m). When gcd(a, m)=1, the coefficient x is the modular inverse.
The final answer is normalized into the range 0 to m-1, so you always get a standard non-negative inverse.
Example
Suppose we want the inverse of 17 mod 43. The result is 38, because:
17 × 38 = 646 ≡ 1 (mod 43)
Why modular inverses matter
- Cryptography: RSA key generation and decryption rely on modular inverses.
- Programming contests: Used with modular division in combinatorics and dynamic programming.
- Algebra and number theory: Fundamental in rings, finite fields, and congruences.
- Error-correcting and coding systems: Frequently used in finite field arithmetic.
Common mistakes to avoid
1) Trying to divide directly modulo m
In modular arithmetic, division is performed by multiplying by an inverse. If the inverse does not exist, the “division” is not valid.
2) Ignoring gcd(a, m)
Always check coprimality first. If a and m share a factor, no inverse exists.
3) Forgetting normalization
The algorithm may produce a negative coefficient. Convert it with (x mod m + m) mod m to get the standard positive representative.
Quick FAQ
Can a negative number have a modular inverse?
Yes. Reduce it first modulo m, then compute the inverse of that residue.
Is the inverse unique?
Yes, unique modulo m whenever it exists.
What if m is prime?
If m is prime, every nonzero residue modulo m has an inverse.