Find the modular multiplicative inverse a⁻¹ mod m using the Extended Euclidean Algorithm with step-by-step EEA table, Euler method, verification, and invertible-elements reference.
The **Inverse Modulo Calculator** finds the modular multiplicative inverse of a number — the value x such that a × x ≡ 1 (mod m). This concept is central to modular arithmetic, cryptography (RSA, Diffie–Hellman), and coding theory. A modular inverse exists if and only if GCD(a, m) = 1, meaning a and m must be coprime.
This tool applies the **Extended Euclidean Algorithm** (EEA) to compute the inverse efficiently, displaying every intermediate quotient, remainder, and Bézout coefficient in a clear step-by-step table. It also supports an alternative derivation through **Euler's theorem**: a^(φ(m)−1) mod m, where φ(m) is Euler's totient function. Both methods are shown side by side so students and developers can compare approaches.
Beyond finding a single inverse, the calculator lists every invertible element modulo m along with its inverse, shows a color-coded multiplication table for small moduli, and lets you verify any candidate answer instantly. Preset examples cover common moduli used in textbooks and cryptographic contexts, making this an all-in-one reference for anyone studying number theory or implementing modular-inverse routines in code.
Computing modular inverses by hand is tedious and error-prone, especially when the Extended Euclidean Algorithm involves many steps. This calculator automates the process while exposing every intermediate calculation, so you can learn the method or verify homework without risk of arithmetic mistakes.
It also goes beyond a bare answer by showing Euler's totient, listing all invertible elements, and rendering a mod-m multiplication table. That broader context helps when you need to understand the structure of Z/mZ (the integers modulo m) rather than just one isolated inverse.
Extended Euclidean Algorithm: express GCD(a, m) = a·s + m·t; if GCD = 1 then a⁻¹ ≡ s (mod m). Euler's method: a⁻¹ ≡ a^(φ(m)−1) (mod m) when GCD(a, m) = 1.
Result: 3⁻¹ mod 7 = 5
GCD(3, 7) = 1, so the inverse exists. EEA yields s = 5, and indeed 3 × 5 = 15 ≡ 1 (mod 7).
The standard Euclidean Algorithm repeatedly divides the larger number by the smaller, keeping the remainder, until the remainder is zero. The last nonzero remainder is the GCD. The **extended** version additionally tracks coefficients s and t (Bézout coefficients) that express GCD(a, m) = a·s + m·t. When GCD = 1, multiplying both sides by 1 shows that a·s ≡ 1 (mod m), so s (reduced mod m) is the modular inverse.
Euler's theorem states that a^φ(m) ≡ 1 (mod m) whenever GCD(a, m) = 1. Dividing both sides by a gives a^(φ(m)−1) ≡ a⁻¹ (mod m). Computing the totient φ(m) requires the prime factorization of m, which can be expensive for large m, but for small m or known-prime m the approach is straightforward and connects the inverse to group theory.
In RSA, the private exponent d is the modular inverse of the public exponent e modulo φ(n). Computing d is exactly the operation this calculator performs. Similarly, in Diffie–Hellman and elliptic-curve cryptography, modular inverses appear when dividing or solving discrete-log-related equations. Understanding how the EEA works is therefore essential for anyone studying or implementing public-key cryptography.
It is the integer x such that a × x ≡ 1 (mod m). It exists only when GCD(a, m) = 1.
If a and m share a common factor d > 1, then a × x is always divisible by d, so it can never equal 1 mod m. That means no residue class can act as a true multiplicative inverse unless a and m are coprime.
It finds integers s and t such that a·s + m·t = GCD(a, m). When GCD = 1, s mod m is the inverse.
By Euler's theorem, a^φ(m) ≡ 1 (mod m) when GCD(a, m) = 1, so a^(φ(m)−1) is the inverse. It is conceptually elegant, but it is most practical when φ(m) is already known or easy to compute.
Yes for large m, because EEA runs in O(log m) steps while computing a^(φ(m)−1) requires knowing φ(m), which involves factoring m. In practice, that makes EEA the default method in most real implementations.
RSA encryption, Diffie–Hellman key exchange, solving linear congruences, the Chinese Remainder Theorem, and error-correcting codes all rely on modular inverses. Any algorithm that needs to "divide" inside modular arithmetic usually depends on this operation.