What is a modular inverse?
The modular multiplicative inverse of an integer a modulo m is an integer x such that \((a \cdot x) \bmod m = 1\). It is the "division" operation of modular arithmetic and is central to number theory, the RSA cryptosystem, and many coding-theory algorithms. This calculator finds x using the extended Euclidean algorithm.
How to use this calculator
Enter the number a and the modulus m (with m ≥ 2). The tool returns the smallest non-negative inverse x in the range 0 ≤ x < m, confirms whether an inverse exists, and shows gcd(a, m). If gcd(a, m) ≠ 1, no inverse exists and the result is reported as "None".
The formula explained
An inverse exists only when \(\gcd(a, m) = 1\), i.e. a and m are coprime. The extended Euclidean algorithm finds integers x and y satisfying \(a \cdot x + m \cdot y = \gcd(a, m)\). When the gcd is 1, reducing x modulo m gives the inverse:
The result is normalized to a positive value by adding m if it is negative.
Worked example
Find the inverse of 3 modulo 11. We need x with \(3x \equiv 1 \pmod{11}\). Testing, \(3 \times 4 = 12 = 11 + 1\), so \(12 \bmod 11 = 1\). Therefore \(x = 4\). The extended Euclidean algorithm returns the same value, and \(\gcd(3, 11) = 1\), confirming the inverse exists.
Step-by-Step: Extended Euclidean Algorithm by Hand
The modular inverse of a modulo m is the number x with \(a \cdot x \equiv 1 \pmod{m}\). It exists only when \(\gcd(a, m) = 1\). The extended Euclidean algorithm finds it in three steps.
- Repeated division. Divide m by a, then divide the previous divisor by the remainder, and so on, until the remainder is 0. The last nonzero remainder is the gcd. If it is not 1, no inverse exists.
- Express 1 as a combination. Work backwards (back-substitution), or track coefficients as you go, to write \(1 = a \cdot x + m \cdot y\). This is the Bézout identity.
- Reduce x. Take \(x \bmod m\). If x is negative, add m (repeat if necessary) to land in the range 0 to m − 1.
Worked example: a = 7, m = 40.
| Step | Division | Quotient q | Remainder |
|---|---|---|---|
| 1 | 40 = 5·7 + 5 | 5 | 5 |
| 2 | 7 = 1·5 + 2 | 1 | 2 |
| 3 | 5 = 2·2 + 1 | 2 | 1 |
| 4 | 2 = 2·1 + 0 | 2 | 0 |
The last nonzero remainder is 1, so \(\gcd(7, 40) = 1\) and an inverse exists.
Back-substitution:
$$1 = 5 - 2\cdot 2 = 5 - 2(7 - 5) = 3\cdot 5 - 2\cdot 7 = 3(40 - 5\cdot 7) - 2\cdot 7 = 3\cdot 40 - 17\cdot 7$$
So \(7 \cdot (-17) + 40 \cdot 3 = 1\), which gives \(x = -17\).
Iterative check (coefficient t of a): start with \(t_0 = 0\) (for m = 40) and \(t_1 = 1\) (for a = 7), then use \(t_{k+1} = t_{k-1} - q_k \, t_k\).
| Remainder | q used | t |
|---|---|---|
| 40 | – | 0 |
| 7 | – | 1 |
| 5 | 5 | 0 − 5·1 = −5 |
| 2 | 1 | 1 − 1·(−5) = 6 |
| 1 | 2 | −5 − 2·6 = −17 |
The row where the remainder reaches 1 gives \(t = -17\). Reduce it: \(-17 + 40 = \)23.
Verification: \(7 \cdot 23 = 161 = 4 \cdot 40 + 1\), so \(161 \bmod 40 = 1\). ✓
The same method works for larger numbers. For a = 17, m = 3120 it gives x = 2753, because \(17 \cdot 2753 = 46801 = 15 \cdot 3120 + 1\). This pair is a classic textbook RSA example.
Example Inputs and Their Inverses
Each inverse below satisfies \((a \cdot x) \bmod m = 1\). When \(\gcd(a, m) > 1\), no inverse exists.
| a | m | gcd(a, m) | Inverse x | Check |
|---|---|---|---|---|
| 3 | 11 | 1 | 4 | 3·4 = 12 = 1·11 + 1 |
| 7 | 26 | 1 | 15 | 7·15 = 105 = 4·26 + 1 |
| 5 | 12 | 1 | 5 | 5·5 = 25 = 2·12 + 1 |
| 10 | 17 | 1 | 12 | 10·12 = 120 = 7·17 + 1 |
| 17 | 3120 | 1 | 2753 | 17·2753 = 46801 = 15·3120 + 1 |
| 4 | 6 | 2 | None | 4x mod 6 is always even, never 1 |
| 6 | 9 | 3 | None | 6x mod 9 is always a multiple of 3, never 1 |
Notice that 5 is its own inverse modulo 12. In general, \(x^2 \equiv 1 \pmod{m}\) has solutions other than 1, so some numbers are self-inverse.
Key Terms: Coprime, GCD, Congruence and Residue
- Modulus (m): the positive integer at which values wrap around, as on a clock face.
- Congruence (≡): \(a \equiv b \pmod{m}\) means m divides \(a - b\), so a and b leave the same remainder when divided by m.
- GCD: the greatest common divisor, the largest integer that divides both numbers.
- Coprime (relatively prime): two integers whose gcd is 1. This is exactly the condition for a modular inverse to exist.
- Bézout identity: for integers a and m there are integers x and y with \(a \cdot x + m \cdot y = \gcd(a, m)\). When the gcd is 1, reducing this equation modulo m gives \(a \cdot x \equiv 1\), so x is the inverse.
- Residue class: the set of all integers sharing the same remainder modulo m. The inverse is unique as a residue class, and the calculator reports the representative from 0 to m − 1.
- Modular multiplicative inverse: the residue \(x = a^{-1} \bmod m\) with \(a \cdot x \equiv 1 \pmod{m}\).
Euler's theorem: if \(\gcd(a, m) = 1\), then \(a^{\varphi(m)} \equiv 1 \pmod{m}\), where \(\varphi\) is Euler's totient function. So the inverse can also be computed as \(a^{\varphi(m)-1} \bmod m\).
Fermat's little theorem: when m = p is prime, \(\varphi(p) = p - 1\), so \(a^{-1} \equiv a^{p-2} \pmod{p}\) for any a not divisible by p. Example: \(3^{9} = 19683 = 1789 \cdot 11 + 4\), so \(3^{-1} \equiv 4 \pmod{11}\), matching the table above. The power formula needs the factorization of m (to find \(\varphi\)), while the extended Euclidean algorithm does not, so it is usually the faster method for general moduli.
FAQ
When does no inverse exist? When a and m share a common factor greater than 1 — for example 4 modulo 6 (gcd = 2) has no inverse.
Does m have to be prime? No. m can be any integer ≥ 2; only coprimality of a and m matters.
What range is the answer in? The inverse is given as the smallest non-negative residue, between 0 and m − 1.