Modular Inverse Calculator
The modular multiplicative inverse of a modulo m is the integer x in the range 0 to m-1 such that a times x is congruent to 1 (mod m). Enter a and m to find the inverse using the extended Euclidean algorithm, which also computes gcd(a,m) and the Bezout coefficients. An inverse exists only when gcd(a,m) = 1. For example, the inverse of 3 mod 7 is 5 because 3 times 5 = 15 = 2 times 7 plus 1. This calculator shows the complete step-by-step working of the extended Euclidean algorithm, which repeatedly applies the division algorithm to find integers x and y satisfying the Bezout identity: a times x + m times y = gcd(a,m). When gcd equals 1, x reduced modulo m is the desired inverse. Modular inverses are used throughout cryptography (RSA decryption, elliptic curve arithmetic), the Chinese Remainder Theorem, and polynomial arithmetic over finite fields.
Extended Euclidean algorithm steps
| Step | Dividend | Divisor | Quotient | Remainder | x | y |
|---|
Algorithm
Extended Euclidean algorithm finds x, y such that:
a * x + m * y = gcd(a, m)
If gcd(a, m) = 1: inverse = x mod m
If gcd(a, m) > 1: no inverse exists
Modular inverse: frequently asked questions
What is a modular multiplicative inverse?
The modular multiplicative inverse of a modulo m is the integer x such that a * x ≡ 1 (mod m). It is written as a^(-1) mod m. For example, the inverse of 3 mod 7 is 5 because 3 * 5 = 15 = 2 * 7 + 1, so 3 * 5 ≡ 1 (mod 7).
When does a modular inverse exist?
A modular inverse of a modulo m exists if and only if gcd(a, m) = 1, meaning a and m are coprime (share no common factor other than 1). If gcd(a, m) is greater than 1, no inverse exists. For example, 4 has no inverse mod 6 because gcd(4,6) = 2.
How is the extended Euclidean algorithm used?
The extended Euclidean algorithm finds integers x and y such that a*x + m*y = gcd(a,m). When gcd(a,m) = 1, this gives a*x + m*y = 1, so a*x ≡ 1 (mod m), making x the modular inverse. The algorithm works by back-substituting from the steps of the ordinary Euclidean algorithm.
Why do we need modular inverses in cryptography?
Modular inverses are essential for decryption in RSA: the private key d satisfies e*d ≡ 1 (mod phi(n)), so d is the modular inverse of e modulo phi(n). They are also used in the Chinese Remainder Theorem, modular division, and computing field inverses in elliptic curve cryptography.
Is the modular inverse unique?
Yes, when it exists, the modular inverse of a modulo m is unique within the range 0 to m-1. Any other solution differs by a multiple of m. This calculator always returns the smallest non-negative inverse.
Sources
- Extended Euclidean algorithm: NIST SP 800-56B Rev. 2.
- Modular arithmetic and inverses: NIST Introduction to Finite Fields.
Reviewed by the CalculatorHub team, edited by James Graham, 14 June 2026. See our methodology.