Inverse Modulo Calculator: Fast Multiplicative & Additive Inverses

How to use the Inverse Modulo Calculator

1. Choose the inverse type. Pick Multiplicative or Additive.
2. Enter integers for a and m. The calculator accepts negative a. It reduces it modulo m.
3. Read the result. You see the smallest non-negative inverse and the full solution class (mod m). If no multiplicative inverse exists you see a plain explanation.
4. Copy or share. Hit Copy to place the value on your clipboard. Paste it into code or notes.

Pro tip: For multiplicative inverse you can paste any integer for a. The tool normalizes it to the range 0…m−1. That saves time and avoids sign mistakes.

When an inverse exists

Multiplicative inverse

• A multiplicative inverse exists only if gcd(a, m) = 1.
• If a and m share a factor greater than 1 there is no solution. Every product a·x stays a multiple of that factor while 1 does not.

Plain test

• Run the greatest common divisor.
• If the gcd equals 1 then the inverse exists.
• If the gcd is not 1 then the inverse does not exist.

Additive inverse

• An additive inverse always exists for m ≥ 1.
• The answer is x ≡ −a (mod m) then normalized to 0…m−1.

Formulas and methods

The calculator uses standard rules from elementary number theory. You can verify each step with trusted references.

1) Extended Euclidean Algorithm (EGCD)

EGCD finds integers u and v such that:

a·u + m·v = gcd(a, m)

• When gcd(a, m) = 1 the identity becomes a·u + m·v = 1.
• Reduce both sides modulo m. The term m·v vanishes so a·u ≡ 1 (mod m).
• Therefore u is a multiplicative inverse. Normalize u into 0…m−1 to return the smallest residue.

Start with: Extended Euclidean algorithm and the modular inverse overview.

2) Fermat’s little theorem (for prime moduli)

If m is prime and a ≢ 0 (mod m) then a^m−1 ≡ 1 (mod m). Hence a^m−2 ≡ a⁻¹ (mod m). Use fast powering rather than literal exponent first then modulo. See Fermat’s little theorem.

3) Euler’s theorem (for coprime pairs)

When gcd(a, m) = 1 we have a^φ(m) ≡ 1 (mod m), where φ is Euler’s totient. Then a^φ(m)−1 is an inverse. EGCD remains simpler for most inputs. Reference: Euler’s theorem.

4) Additive inverse rule

For m ≥ 1 the rule is straightforward: x ≡ −a (mod m), then bring the result into 0…m−1.

Worked examples

These examples mirror the calculator’s output so you can double-check by hand.

Example A — multiplicative inverse exists

Find: inverse of a = 5 modulo m = 9

1. gcd(5, 9) = 1 so the inverse exists.
2. Solve 5·u + 9·v = 1 by EGCD. One pair is u = 2, v = −1 because 5·2 + 9·(−1) = 10 − 9 = 1.
3. Normalize u modulo 9. 2 mod 9 = 2.
4. Answer: x = 2.
5. Check: 5 × 2 = 10 ≡ 1 (mod 9).

Plain language: Multiplying by 2 undoes multiplication by 5 when you work mod 9. Every step wraps at 9 so 10 becomes 1.

Example B — multiplicative inverse does not exist

Find: inverse of a = 55 modulo m = 99

1. gcd(55, 99) = 11 not 1.
2. Every multiple of 55 is also a multiple of 11.
3. The number 1 is not a multiple of 11.
4. Therefore 55 × x can never land on 1 modulo 99. There is no inverse.

What to try instead: pick values that are coprime. For instance gcd(55, 98) = 1 so an inverse exists mod 98.

Example C — additive inverse

Find: additive inverse of a = 5 modulo m = 9

The rule says x ≡ −5 (mod 9). Normalize −5 into 0…8. −5 mod 9 = 4. Answer: x = 4 because 5 + 4 = 9 ≡ 0 (mod 9).

Snippet answers for quick wins

How do you find the multiplicative inverse of a modulo m?

1. Compute gcd(a, m). If it is not 1 the inverse does not exist.
2. Use EGCD to get u, v with a·u + m·v = 1.
3. The inverse is x ≡ u (mod m) then normalize to 0…m−1.
4. Check with a × x ≡ 1 (mod m).

What is the additive inverse of a modulo m?

The additive inverse is x ≡ −a (mod m). Normalize to 0…m−1. It always exists for m ≥ 1.

Real-world uses

• Cryptography. RSA and many signature schemes rely on modular inverses during key generation and signing steps.
• Number-theory problems. Linear congruences, Chinese Remainder Theorem applications, and contest problems use inverses constantly.
• Error-correcting codes. Finite-field arithmetic depends on inverses to decode data robustly.
• Computer graphics. Modular arithmetic appears in hashing and random number generators where inverses improve mixing properties.

Pseudocode and quick implementations

Use these short snippets when you prefer code over a calculator. They follow the same rules.

EGCD and modular inverse (language-agnostic pseudocode)

// returns (g, x, y) with a*x + b*y = g = gcd(a, b)
function egcd(a, b):
    x0 = 1; y0 = 0
    x1 = 0; y1 = 1
    r0 = a; r1 = b
    while r1 ≠ 0:
        q  = floor(r0 / r1)
        (r0, r1) = (r1, r0 - q*r1)
        (x0, x1) = (x1, x0 - q*x1)
        (y0, y1) = (y1, y0 - q*y1)
    return (abs(r0), x0, y0)

// multiplicative inverse of a modulo m (if it exists)
function modInverse(a, m):
    (g, x, y) = egcd(a mod m, m)
    if g ≠ 1: return null
    return (x mod m + m) mod m

Python one-liners

# Python 3.8+: multiplicative inverse using pow when m is prime
inv = pow(a, m-2, m)  # valid if m is prime and a % m != 0

# General case with EGCD
def inv_mod(a, m):
    a %= m
    x0, x1, r0, r1 = 1, 0, a, m
    while r1:
        q = r0 // r1
        x0, x1, r0, r1 = x1, x0 - q*x1, r1, r0 - q*r1
    if r0 != 1:
        return None
    return x0 % m

JavaScript quick version

function invMod(a, m){
  a = ((a % m) + m) % m;
  let x0 = 1, x1 = 0, r0 = a, r1 = m;
  while (r1 !== 0){
    const q = (r0 / r1) | 0;
    [r0, r1] = [r1, r0 - q * r1];
    [x0, x1] = [x1, x0 - q * x1];
  }
  if (r0 !== 1) return null;
  return (x0 % m + m) % m;
}

Troubleshooting and common mistakes

• Using m = 1. There is no multiplicative inverse modulo 1. Units do not exist in that ring.
• Forgetting to normalize negatives. Reduce a first: a ← a mod m.
• Confusing additive and multiplicative inverses. The requirements differ. Additive always exists for m ≥ 1. Multiplicative requires coprime input.
• Computing large powers naively. If you use Fermat’s trick for prime moduli call fast powering: repeated squaring with modulus each step.
• Copying the wrong solution form. Always state the result as a residue class: x ≡ r (mod m). Then include the smallest non-negative representative.

Frequently asked questions

What does “mod” mean in plain English?

“Mod” is short for modulo. Two numbers are congruent mod m when they have the same remainder after division by m. Example: 17 ≡ 5 (mod 12) because both leave remainder 5 after division by 12.

Can the multiplicative inverse be zero?

No. If x = 0 then a × x ≡ 0 not 1.

Why does gcd decide existence?

If gcd(a, m) = d > 1 then every product a × x is a multiple of d. The number 1 is not a multiple of d. You cannot solve a × x ≡ 1 (mod m) in that case.

Is there a faster way for prime moduli?

Yes. Use x ≡ a^m−2 (mod m) from Fermat’s little theorem. It works when m is prime and a is not divisible by m.

What if a is negative?

Reduce first: a ← a mod m. After that run the usual method.

Does the additive inverse ever fail?

No for m ≥ 1. The answer is always x ≡ −a (mod m).