What is a multiplicative inverse modulo m?
The modular multiplicative inverse of an integer a modulo m is an integer x in the range 1 to m−1 such that \((a \cdot x) \bmod m = 1\). In other words, multiplying a by x and dividing by m leaves a remainder of exactly 1. This is the modular-arithmetic equivalent of dividing by a, and it is a cornerstone of number theory and cryptography (RSA key generation, hashing, the Chinese Remainder Theorem, and more).
How to use this calculator
Enter the integer a and the modulus m (m must be 2 or greater). The calculator reduces a modulo m, runs the extended Euclidean algorithm, and returns the inverse if one exists. Negative values of a are handled automatically by reducing them into the range 0 to m−1.
The formula explained
An inverse exists if and only if \(\gcd(a, m) = 1\) — that is, a and m share no common factor other than 1 (they are coprime):
$$\text{a} \cdot x \equiv 1 \pmod{\text{m}}, \quad x \text{ exists } \iff \gcd\!\left(\text{a},\, \text{m}\right) = 1$$The extended Euclidean algorithm finds integers s and t satisfying \(a \cdot s + m \cdot t = \gcd(a, m)\). When the gcd is 1, the coefficient s reduced modulo m is the inverse. If \(\gcd(a, m) \neq 1\), no inverse exists.
Worked example
Find the inverse of 3 modulo 11. We need x with \((3 \cdot x) \bmod 11 = 1\). Testing, \(3 \cdot 4 = 12\), and \(12 \bmod 11 = 1\). So the inverse is 4. The extended Euclidean algorithm gives the same result instantly because \(\gcd(3, 11) = 1\).
FAQ
When does no inverse exist? When a and m are not coprime. For example, 4 has no inverse mod 8 because \(\gcd(4, 8) = 4 \neq 1\).
Does the modulus need to be prime? No. Any modulus works as long as a is coprime to it. If m is prime, every nonzero a from 1 to m−1 has an inverse.
Why is the result always between 1 and m−1? Because we reduce the inverse modulo m to give the canonical least positive representative.
