Find x such that ax ≡ 1 (mod m) with full Extended Euclidean Algorithm steps, Euler theorem method, brute-force verification, Bézout identity, and all inverse pairs table.
The **Multiplicative Inverse Modulo Calculator** finds the integer x satisfying ax ≡ 1 (mod m) — the modular multiplicative inverse of a modulo m. This relationship is fundamental in number theory, cryptography (RSA key generation, Diffie–Hellman), and computer science (hash functions, error correction). An inverse exists exactly when GCD(a, m) = 1.
Three independent methods confirm the answer. The **Extended Euclidean Algorithm** (EEA) computes Bézout coefficients s, t such that a·s + m·t = GCD(a, m); when GCD = 1, s mod m is the inverse. The **Euler's theorem** approach derives a^(φ(m)−1) mod m. A **brute-force scan** checks every x from 0 to m − 1 as an independent verification. Each step of the EEA is presented in a detailed table showing quotients, remainders, and running Bézout coefficients so students can follow the algorithm by hand.
Beyond the single-answer computation, the calculator lists every inverse pair in ℤ/mℤ, highlights self-inverse elements, shows the general solution family x ≡ inv + k·m, and displays a bar indicating what fraction of elements are invertible — which equals φ(m)/(m − 1). Presets cover common textbook moduli (7, 11, 13, 26, 43) for instant exploration.
Computing modular inverses manually through the Extended Euclidean Algorithm is error-prone, especially for larger moduli. This calculator automates the work while exposing every intermediate step, so you can learn or verify homework without risking arithmetic mistakes.
It also offers three cross-checking methods. If EEA, Euler, and brute-force all agree, you can be confident the answer is correct — useful when debugging cryptographic code or verifying hand computations before an exam.
Extended Euclidean: a·s + m·t = GCD(a,m); if GCD = 1 then x = s mod m. Euler: x = a^(φ(m)−1) mod m. Brute force: scan x ∈ [0, m) until a·x mod m = 1.
Result: x = 5 (since 3 × 5 = 15 ≡ 1 mod 7)
GCD(3, 7) = 1, so the inverse exists. The EEA yields Bézout coefficient s = 5, and indeed 3 × 5 mod 7 = 1. Euler confirms: 3^(6−1) mod 7 = 3^5 mod 7 = 243 mod 7 = 5.
The standard Euclidean Algorithm finds GCD(a, m) by repeated division. The extended version tracks two auxiliary sequences (s and t) that express each intermediate remainder as a linear combination of the original inputs: r_i = a·s_i + m·t_i. When the algorithm terminates with GCD = 1, the coefficient s gives us a·s ≡ 1 (mod m), so s mod m is the modular inverse.
In RSA, the public exponent e and the secret exponent d satisfy e·d ≡ 1 (mod λ(n)), where λ is the Carmichael function of the RSA modulus n. Computing d is precisely the modular-inverse problem this calculator solves. Any error in that computation would generate an invalid private key, which is why independent cross-checks (EEA vs Euler vs brute-force) are standard practice in crypto libraries.
An element a is *self-inverse* (also called an involution) if a² ≡ 1 (mod m). For prime m, the only self-inverse elements are 1 and m − 1, by Lagrange's theorem applied to the polynomial x² − 1. For composite m, additional self-inverse elements may exist, and their number relates to the factorization of m.
It means that a times x leaves remainder 1 when divided by m. Equivalently, a·x − 1 is divisible by m.
When GCD(a, m) > 1. In that case, a·x is always divisible by GCD(a,m) and can never equal 1 mod m.
Both solve the same problem. This version emphasizes the step-by-step EEA table, Bézout identity, and three-method cross-check; the other focuses on the multiplication table and scan.
Cross-checking EEA, Euler, and brute-force gives confidence the answer is correct and illustrates the mathematical connections between the approaches. It also helps you see which method is easiest to use by hand, which is especially helpful in class or while debugging code.
All solutions form the congruence class x ≡ inv (mod m), meaning x = inv, inv + m, inv + 2m, ... The calculator displays the first five.
An element a where a × a ≡ 1 (mod m). For example, 1 and m−1 are always self-inverse when coprime to m.