Modular Inverse Calculator – Extended Euclidean Algorithm Explained
The modular multiplicative inverse of an integer a modulo m is the integer x that satisfies (a × x) mod m = 1. It plays the same role in modular arithmetic that a reciprocal plays in ordinary arithmetic — instead of dividing by a, you multiply by its inverse. This calculator finds that inverse using the Extended Euclidean Algorithm, shows every row of the working, verifies the result, and can also solve linear congruences or build a full inverse lookup table.
When Does an Inverse Exist?
A modular inverse of a exists modulo m if and only if a and m are coprime — that is, gcd(a, m) = 1. If they share any common factor greater than 1, no multiple of a can ever land exactly on 1 modulo m, so the calculator reports that no inverse exists along with the shared GCD instead of returning a meaningless number.
How the Extended Euclidean Algorithm Works
The plain Euclidean algorithm finds gcd(a, m) by repeatedly replacing the larger value with the remainder of dividing it by the smaller one. The extended version tracks two extra running coefficients, s and t, at every row so that a·s + m·t always equals that row's remainder — an identity known as Bezout's identity. When the remainder finally reaches 1, its s coefficient, reduced into the range [0, m), is exactly the modular inverse. Because both the GCD and the Bezout coefficients fall out of the same table, the calculator can show the full working in a single pass rather than a separate back-substitution step.
a and m, there exist integers x and y such that a·x + m·y = gcd(a, m). When the GCD is 1, that x (taken modulo m) is the modular inverse.Solving Linear Congruences
An equation of the form ax ≡ b (mod m) is a linear congruence, and it has a single solution modulo m whenever gcd(a, m) = 1. The congruence solver mode finds the inverse of a first, then computes x = (inverse(a, m) × b) mod m. If a and m are not coprime, this approach cannot produce a single answer, and the tool explains why rather than guessing.
Batch Inverse Tables
Many applications — building lookup tables, checking which residues are units in a ring, or preparing an affine cipher key — need the inverse of several numbers under the same modulus at once. Batch mode runs the same Extended Euclidean computation across every value you list, flags any entry that has no inverse, and reports invalid tokens individually so one typo never blocks the rest of the table.
Why It Matters in Cryptography
Modular inverses are a working ingredient of RSA key generation: the private decryption exponent is computed as the modular inverse of the public encryption exponent, taken modulo Euler's totient of the RSA modulus. The same operation underlies error-correcting codes, hash-based data structures, and any scheme that needs to reverse a multiplication performed modulo m. Because these moduli can run to hundreds of digits, this calculator parses every value as a BigInt so precision never degrades the way ordinary floating-point numbers would past 2^53.
Reading the Output and Limits
Every mode shows a clear inverse-or-not verdict, the GCD that explains it, and a verification line confirming (a × inverse) mod m = 1. The step table displays each row of the Extended Euclidean Algorithm together with its running Bezout coefficients, and results can be copied, downloaded as text or CSV, or shared through a link that restores every input. Values accept up to 300 digits each; a modulus of exactly 1 is treated as a degenerate case (every integer is congruent to 0) rather than an error, and a = 0 is always reported as having no inverse for any modulus greater than 1.