Multiplicative Inverse Modulo Calculator
Enter a value and a modulus to find the multiplicative inverse mod m, the unique x such that a times x is congruent to 1 (mod m). The calculator also finds the additive inverse and shows every step of the Extended Euclidean Algorithm so you can follow the working. Switch modes to choose multiplicative or additive, and enable the Fermat shortcut for prime moduli.
What is a multiplicative inverse modulo m?
The multiplicative inverse of an integer a modulo m is another integer x such that a times x is congruent to 1 (mod m). Written more compactly: a * x = 1 mod m, or equivalently a * x - 1 is exactly divisible by m. This mirrors the ordinary reciprocal (1/a) in regular arithmetic, but stays within the world of integers. The key restriction is that x must itself be an integer, so it only exists when a and m share no common factor other than 1, that is, when GCD(a, m) = 1. When the inverse does exist it is unique within the range [0, m-1], and every other valid x differs from it by a multiple of m.
How to find the inverse: Extended Euclidean Algorithm
The Extended Euclidean Algorithm is the standard method and works for any coprime pair. It extends the ordinary GCD calculation to also track integer coefficients x and y satisfying the linear equation a*x + m*y = GCD(a, m). When GCD equals 1, the coefficient x is exactly the modular inverse. The algorithm iteratively applies division with remainder, then back-substitutes to express 1 as a linear combination of a and m. Back-substituting can feel fiddly by hand, so using the steps panel in this calculator lets you verify each division and coefficient update in sequence. Fermat's Little Theorem offers a shortcut for prime moduli: when m is prime, a^(m-2) mod m gives the inverse directly, avoiding the back-substitution entirely. This is especially convenient in cryptographic routines that already rely on modular exponentiation.
Additive inverse vs. multiplicative inverse
The additive inverse of a mod m is the integer x in [0, m-1] such that a + x is congruent to 0 (mod m). It always equals (m - (a mod m)) mod m and always exists regardless of GCD. By contrast, the multiplicative inverse requires coprimality. Choosing "Additive inverse" mode in this calculator shows the negation of a in modular arithmetic, which is useful when implementing subtraction over a finite field or a cyclic group.
Why modular inverses matter: cryptography and number theory
Modular multiplicative inverses underpin much of modern public-key cryptography. In RSA, the private exponent d is the multiplicative inverse of the public exponent e modulo the Euler totient of the modulus. In elliptic-curve cryptography, point division on a curve over a prime field reduces to multiplying by a modular inverse. Solving linear congruences of the form a*x = b (mod m) also requires the inverse: the solution is x = b * a^(-1) mod m, provided GCD(a, m) divides b. Beyond cryptography, inverses appear in the Chinese Remainder Theorem, in computing Bezout coefficients, and in discrete Fourier transforms over finite fields.
Multiplicative inverse table mod 11 (prime modulus)
| a | a^(-1) mod 11 | Check: a x a^(-1) mod 11 |
|---|---|---|
| 1 | 1 | 1 |
| 2 | 6 | 1 |
| 3 | 4 | 1 |
| 4 | 3 | 1 |
| 5 | 9 | 1 |
| 6 | 2 | 1 |
| 7 | 8 | 1 |
| 8 | 7 | 1 |
| 9 | 5 | 1 |
| 10 | 10 | 1 |
Since 11 is prime, every integer 1 through 10 has a unique multiplicative inverse mod 11.
Frequently asked questions
When does a multiplicative inverse modulo m exist?
The multiplicative inverse of a modulo m exists if and only if a and m are coprime, meaning GCD(a, m) = 1. If they share a common factor greater than 1, no integer x can satisfy a*x = 1 (mod m). When m is prime every integer from 1 to m-1 is coprime with m, so every such integer has an inverse.
What is Fermat's Little Theorem shortcut?
When the modulus m is a prime number, Fermat's Little Theorem states that a^(m-1) is congruent to 1 (mod m) for any a not divisible by m. Multiplying both sides by a^(-1) gives a^(m-2) = a^(-1) (mod m), so computing a raised to the power m-2 (mod m) directly yields the inverse. This is efficient because modular exponentiation can be done in O(log m) multiplications using repeated squaring.
Is the modular inverse unique?
Within any complete residue system [0, m-1] the inverse is unique. There is exactly one x in that range satisfying a*x = 1 (mod m). Adding any multiple of m produces another valid but equivalent integer, since congruence mod m treats them as identical.
How do I use the inverse to solve a linear congruence?
To solve a*x = b (mod m): first check that GCD(a, m) divides b, otherwise there is no solution. If it does, find the multiplicative inverse of a (call it a_inv) and compute x = b * a_inv mod m. That gives the smallest non-negative solution; the full set of solutions is x + k*(m/GCD(a,m)) for any integer k.
What is the additive inverse modulo m?
The additive inverse of a modulo m is the value x in [0, m-1] such that a + x is divisible by m. It equals (-a) mod m, which simplifies to m - (a mod m) when a is not already divisible by m, and to 0 when it is. Unlike the multiplicative inverse, the additive inverse always exists.
Why does GCD(a, m) have to equal 1?
Suppose d = GCD(a, m) > 1, and assume a*x = 1 (mod m) for some integer x. Then m divides a*x - 1. Since d divides both a and m, d divides a*x, so d divides (a*x - 1) - a*x = -1, giving d = 1, a contradiction. That shows no such x can exist whenever d > 1.