Modular Inverse Calculator

The modular inverse of a integer a modulo m is an integer x such that a * x is congruent to 1 (mod m). In other words, when you multiply a by x and divide by m, the remainder is exactly 1. The inverse is usually written as a^-1 mod m and is unique inside the range [0, m - 1] whenever it exists. It plays the role that 1 / a plays in ordinary arithmetic: it undoes multiplication. For example, 3 * 4 = 12 = 1 + 11, so 3 * 4 is congruent to 1 mod 11, which means 4 is the inverse of 3 mod 11. Modular inverses show up everywhere modular arithmetic does: cryptography (RSA, Diffie-Hellman), error-correcting codes, hashing, the Chinese Remainder Theorem, and any time you need to divide inside Z/mZ.

A modular inverse of a mod m exists if and only if gcd(a, m) = 1, that is, when a and m are coprime (share no common factor other than 1). If gcd(a, m) = d with d greater than 1, then every multiple of a mod m is also a multiple of d, so the product a * x mod m can only ever land on multiples of d. Since 1 is not a multiple of d (when d is greater than 1), no x can produce 1. Concrete example: 6 has no inverse mod 9, because gcd(6, 9) = 3, and the multiples of 6 mod 9 are {0, 3, 6, 0, 3, 6, ...}. They never hit 1. This calculator flags exactly that case and reports the gcd so you can see which factor is blocking the inverse.

The extended Euclidean algorithm finds integers s and t such that s * a + t * m = gcd(a, m). When gcd(a, m) = 1, that identity becomes s * a + t * m = 1, and taking both sides mod m gives s * a is congruent to 1 (mod m), so s is the inverse of a (after normalizing into [0, m - 1]). The iterative version maintains three rows (r, s, t) that always satisfy s * a + t * m = r, starting from (m, 0, 1) and (a, 1, 0). At every step, divide the previous r by the current r, take the quotient q, and subtract q times the current row from the previous row to get the next row. When r reaches 0, the previous row is (gcd, s, t). It is the same algorithm that computes gcd, but it tracks how that gcd was assembled from a and m, which is exactly the witness you need for the inverse.

In RSA, the public key is a pair (n, e) where n = p * q is the product of two large primes and e is a public exponent (commonly 65537). The private key d is the modular inverse of e modulo phi(n), where phi(n) = (p - 1)(q - 1) is Euler's totient. Encryption is c = m^e mod n; decryption is m = c^d mod n. The reason it works is that e * d is congruent to 1 (mod phi(n)), which by Euler's theorem means (m^e)^d = m^(e*d) is congruent to m (mod n). The whole security model rests on the assumption that anyone who knows n but not its factorization cannot compute phi(n), and so cannot compute d = e^-1 mod phi(n). Key generation calls the extended Euclidean algorithm exactly once to invert e modulo phi(n) and produce the private key.

Sure. We want x with 3 * x is congruent to 1 (mod 11). Run the extended Euclidean algorithm on (a, m) = (3, 11). Start with rows (11, 0, 1) and (3, 1, 0). Step 1: q = floor(11 / 3) = 3, so the next row is (11 - 3 * 3, 0 - 3 * 1, 1 - 3 * 0) = (2, -3, 1). Step 2: q = floor(3 / 2) = 1, next row is (3 - 1 * 2, 1 - 1 * (-3), 0 - 1 * 1) = (1, 4, -1). Step 3: q = floor(2 / 1) = 2, next row is (2 - 2 * 1, -3 - 2 * 4, 1 - 2 * (-1)) = (0, -11, 3). The previous row (1, 4, -1) is (gcd, s, t), and indeed 4 * 3 + (-1) * 11 = 12 - 11 = 1. So the inverse is s = 4, already in [0, 10]. Check: 3 * 4 = 12 = 1 + 11, so 3 * 4 is congruent to 1 mod 11. The calculator runs exactly these steps and shows you the table.