Find the Modular Multiplicative Inverse
Enter integers a and m to compute a-1 mod m. The inverse exists only when gcd(a, m) = 1.
Tip: Negative values for a are allowed. The calculator automatically normalizes them into the range 0 to m-1.
What Is a Modular Inverse?
In modular arithmetic, the modular inverse of a number a modulo m is a number x such that:
(a × x) mod m = 1
Think of it as the “division” counterpart in modular systems. If the inverse exists, multiplying by it undoes multiplication by a under modulus m.
When Does the Inverse Exist?
A modular inverse exists if and only if a and m are coprime:
- gcd(a, m) = 1 → inverse exists
- gcd(a, m) ≠ 1 → inverse does not exist
Example:
- a = 3, m = 11: gcd(3, 11) = 1, inverse exists (it is 4).
- a = 6, m = 15: gcd(6, 15) = 3, inverse does not exist.
How This Calculator Works
1) Normalize the input
If a is negative, it is converted to an equivalent positive residue: anorm = ((a mod m) + m) mod m.
2) Run the Extended Euclidean Algorithm
The Extended Euclidean Algorithm finds integers x and y such that:
a·x + m·y = gcd(a, m)
If gcd is 1, then a·x + m·y = 1, so a·x ≡ 1 (mod m). That means x is the inverse (possibly after reducing modulo m).
3) Report inverse or no-inverse result
If gcd is not 1, no modular inverse can satisfy the equation.
Why Modular Inverses Matter
- Cryptography: RSA key generation and signing rely heavily on modular inverses.
- Number theory: Solving congruences and using the Chinese Remainder Theorem.
- Programming contests: Fast division in modular fields (especially with prime moduli).
- Computer algebra: Polynomial and matrix calculations in finite structures.
Quick Worked Example
Find inverse of 17 mod 43:
- 43 = 2×17 + 9
- 17 = 1×9 + 8
- 9 = 1×8 + 1
- 8 = 8×1 + 0
gcd(17, 43) = 1, so inverse exists. Back-substitution gives inverse 38 (since 17×38 = 646 ≡ 1 mod 43).
Common Mistakes to Avoid
- Trying to find an inverse when gcd(a, m) is not 1.
- Using modulus m = 0 or m = 1 for standard inverse operations.
- Forgetting to reduce negative results into the range 0 to m-1.
- Confusing ordinary division with modular inverse operations.
FAQ
Can modulus be negative?
In most definitions, modulus is positive. This tool converts negative modulus input to its absolute value.
Can I use very large integers?
Yes. This calculator uses JavaScript BigInt, so it can handle very large whole numbers.
What if a = 0?
Zero has no multiplicative inverse modulo m (for m > 1), because 0 multiplied by anything is still 0, never 1 modulo m.