Inverse Modulo Calculator

About the Inverse Modulo Calculator

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 page 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. Preset examples cover common moduli used in textbooks and cryptographic contexts, making the page a compact reference for anyone studying number theory or implementing modular-inverse routines in code.

When This Page Helps

Computing modular inverses by hand is tedious, especially when the Extended Euclidean Algorithm involves many steps. This calculator exposes every intermediate calculation, so you can learn the method or verify homework without losing the arithmetic structure.

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.

How to Use the Inputs

1. Enter the value a whose inverse you want to find.
2. Enter the modulus m and keep it positive.
3. Select EEA or Euler's Theorem as the computation method.
4. Read the Modular Inverse output card for the answer, or see why no inverse exists.
5. Optionally type a candidate in the Verify field to confirm it satisfies a × x ≡ 1 (mod m).
6. Review the EEA Steps table to follow the algorithm step by step.
7. Scroll down to the multiplication table (for m ≤ 20) to see all products mod m at once.

Example Calculation

Tips & Best Practices

• If GCD(a, m) ≠ 1, no inverse exists — try a different value or modulus.
• Use presets for common textbook and crypto examples.
• The multiplication table highlights cells equal to 1 in green — each is an inverse pair.
• Verify your hand-computed answer by entering it in the Verify field.
• For prime m, every nonzero a has an inverse because GCD(a, p) = 1 for all 1 ≤ a < p.
• Use the invertible-elements table to quickly see all inverse pairs for a given modulus.

Understanding the Extended Euclidean Algorithm

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 Approach

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.

Practical Cryptographic Applications

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.

Frequently Asked Questions

• What is a modular multiplicative inverse?

  It is the integer x such that a × x ≡ 1 (mod m). It exists only when GCD(a, m) = 1.

• Why does the inverse require GCD = 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.

• How does the Extended Euclidean Algorithm find the inverse?

  It finds integers s and t such that a·s + m·t = GCD(a, m). When GCD = 1, s mod m is the inverse.

• What is Euler's totient method?

  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.

• Is the EEA method always faster?

  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.

• Where are modular inverses used in practice?

  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.