What is the Modular Multiplicative Inverse Calculator?
This calculator finds the modular multiplicative inverse of an integer a modulo m — the unique integer x in the range \(0 \le x < m\) such that \(a \cdot x \equiv 1 \pmod{m}\). It uses the Extended Euclidean Algorithm, which also returns the greatest common divisor \(\gcd(a, m)\). This is pure number theory and works identically everywhere; it is widely used in cryptography (RSA key generation), hashing, and solving linear congruences.
How to use it
Enter the integer a and a positive modulus m (use \(m \ge 2\) for a meaningful unique inverse). The tool reduces a modulo m, runs the Extended Euclidean Algorithm, and reports the inverse together with \(\gcd(a, m)\). If a and m are not coprime (\(\gcd \ne 1\)) there is no inverse and the calculator says so.
The formula explained
The inverse exists if and only if \(\gcd(a, m) = 1\). The Extended Euclidean Algorithm finds integers s and t with \(a \cdot s + m \cdot t = \gcd(a, m)\). When the gcd is 1, \(a \cdot s \equiv 1 \pmod{m}\), so the inverse is $$x = ((s \bmod m) + m) \bmod m,$$ normalized to the least non-negative residue.
Worked example
For \(a = 7\), \(m = 4\): since \(7 \equiv 3 \pmod{4}\), we solve \(3x \equiv 1 \pmod{4}\). The Extended Euclidean Algorithm on \((7, 4)\) yields \(\gcd = 1\) and Bezout coefficient \(s = -1\), so $$x = ((-1 \bmod 4) + 4) \bmod 4 = 3.$$ Check: \(7 \cdot 3 = 21 = 5 \cdot 4 + 1 \equiv 1 \pmod{4}\). The answer is 3.
FAQ
When does an inverse not exist? Only when \(\gcd(a, m) > 1\). For example \(a = 6\), \(m = 9\) has \(\gcd = 3\), so no inverse exists.
Can a be negative or larger than m? Yes. We first reduce a modulo m; the result is unchanged because \(a \equiv a' \pmod{m}\).
What if m = 1? Every integer is congruent to 0 modulo 1, so the inverse is trivially 0.
