What is a Modular Inverse?
In modular arithmetic, the modular inverse of an integer a modulo m is an integer x such that:
a · x ≡ 1 (mod m)
This means that a·x − 1 is divisible by m. The modular inverse exists if and only if gcd(a, m) = 1 (a and m are coprime). The inverse is unique modulo m, and it's a cornerstone of modular arithmetic, playing an essential role in public-key cryptography (RSA), solving linear congruences, and digital signature algorithms (ECDSA).
The Extended Euclidean Algorithm finds integers x, y such that:
a·x + m·y = gcd(a, m)
When gcd(a,m)=1, the coefficient x is exactly the modular inverse of a modulo m.
Historical & Mathematical Authority
The Euclidean algorithm dates back to Euclid's "Elements" (circa 300 BCE), making it one of the oldest surviving algorithms. The Extended Euclidean Algorithm was refined by mathematicians such as Étienne Bézout (1730–1783), who formalized Bézout's identity. In modern number theory and cryptography, the extended algorithm is indispensable: for instance, RSA encryption relies on computing d ≡ e⁻¹ mod φ(N). The algorithm's elegance lies in its linear time complexity O(log min(a,m)) and its deterministic nature.
This tool implements the iterative version of the extended Euclidean algorithm, providing full transparency into the quotients, remainders, and coefficient updates at each step. It supports arbitrarily large integers via JavaScript BigInt, ensuring precision even for cryptographic-scale numbers (up to thousands of bits).
Applications Across Domains
-
Cryptography: RSA key generation, ElGamal, and Diffie-Hellman require modular inverses for private key operations.
-
Computer Algebra: Solving linear congruences, Chinese Remainder Theorem (CRT) reconstruction, modular division.
-
Programming Contests: Efficient modular arithmetic under prime moduli (Fermat's little theorem for prime m).
-
Coding Theory: BCH codes and Reed–Solomon error correction use modular inverses in finite fields.
-
Game Development & Random Number Generation: Linear congruential generators (LCG) sometimes require modular inverses for reversing sequences.
Step-by-Step Algorithm Explanation
The Extended Euclidean Algorithm maintains a table of quotients and updates two pairs of coefficients (s, t) such that at each stage, a·s + m·t = current remainder r. When the remainder becomes 1, the corresponding s (mod m) is the modular inverse. The process is systematic and deterministic:
-
Initialize: (r0, r1) = (m, a), (s0, s1) = (1, 0), (t0, t1) = (0, 1).
-
While r1 ≠ 0: compute quotient q = r0 // r1, remainder r2 = r0 - q·r1, update sequences: (s2, t2) = (s0 - q·s1, t0 - q·t1).
-
Shift: (r0, r1) = (r1, r2) and similarly for coefficients.
-
At termination, r0 = gcd(a,m); if r0 = 1, then s0 (mod m) is the modular inverse.
The interactive table below visualizes each iteration, helping learners internalize the algorithm.
Example Use Cases & Case Study: RSA Decryption
Real-World Cryptography: RSA Private Key
In the RSA cryptosystem, you choose two primes p, q, compute N = p·q, and φ(N) = (p-1)(q-1). Select encryption exponent e with gcd(e, φ(N)) = 1. The decryption exponent d is the modular inverse: d ≡ e⁻¹ mod φ(N). For example, take p=61, q=53 → N=3233, φ(N)=3120. Choose e=17. Compute d ≡ 17⁻¹ mod 3120 = 2753. Using our calculator, you can verify that (17 * 2753) mod 3120 = 1. This inverse makes RSA decryption feasible and secure. Without the extended Euclidean algorithm, asymmetric cryptography would be impossible.
Properties & Theorems
-
Uniqueness: If an inverse exists modulo m, it is unique in the residue class modulo m.
-
Fermat's Little Theorem: For prime modulus p and a not divisible by p, a⁻¹ ≡ a^(p-2) (mod p). Useful for prime moduli but less efficient for large exponents.
-
Euler's Theorem: a^φ(m) ≡ 1 (mod m) when gcd(a,m)=1, leading to a⁻¹ ≡ a^(φ(m)-1) (mod m).
-
Negative Numbers: The calculator reduces negative a to its canonical residue (0 ≤ a < m) before computing inverse, then returns the inverse in the range [1, m-1].
Common Misconceptions & Pitfalls
-
"Every number has a modular inverse" → False. The inverse exists only if gcd(a,m)=1. For example, 2 mod 4 has no inverse.
-
"Inverse is always smaller than modulus" → True, as we usually present the canonical representative between 1 and m-1.
-
"Extended Euclidean algorithm only works for small numbers" → No, it works for arbitrary-size integers (BigInt used here).
-
"Modular inverse is the same as reciprocal" → Only in real numbers; modular arithmetic is a discrete ring.
Performance & Numerical Stability
Our implementation uses native BigInt for arbitrary precision — you can compute inverses for numbers up to thousands of bits, limited only by browser memory. The extended Euclidean algorithm runs in O(log min(a,m)) steps, making it extremely fast even for cryptographic sizes (e.g., 2048-bit RSA parameters).
Trusted mathematical reference – This tool implements the standard iterative extended Euclidean algorithm as described in Introduction to Algorithms (CLRS) and Concrete Mathematics (Graham, Knuth, Patashnik). The algorithm's correctness is proven via invariant maintenance, and our output is validated against known libraries. Reviewed by the GetZenQuery Tech team, last updated April 2026.
Frequently Asked Questions
This happens when gcd(a, m) ≠ 1. For the inverse to exist, a and m must be coprime (share no common factor greater than 1).
The calculator normalizes a modulo m to a positive residue first. For example, -5 mod 12 becomes 7, then computes inverse of 7 mod 12, which is 7 because 7*7=49≡1 mod12.
Modulus must be at least 2. For modulus 1, every integer is congruent to 0, and the inverse is not meaningful. The calculator shows an error.
For prime moduli, Fermat's theorem a^(p-2) mod p yields the inverse, but exponentiation is O(log p) multiplications. The extended Euclidean algorithm is typically faster and does not require primality. Both are efficient, but EEAlg works for any coprime pair.
The calculator uses JavaScript BigInt, supporting integers up to several thousand decimal digits (limited by memory and browser's BigInt implementation). This covers all practical cryptographic and mathematical applications.