inverse modulo calculator

What is an inverse modulo?

In modular arithmetic, the inverse of a number a modulo m is another number x that makes the product equal to 1 under modulo m:

a · x ≡ 1 (mod m)

You can think of it as the modular version of division. Since ordinary division is not always valid in modular systems, we multiply by the modular inverse instead. This is one of the most important tools in number theory, cryptography, and algorithm design.

When does a modular inverse exist?

A modular inverse exists if and only if a and m are coprime, meaning:

gcd(a, m) = 1

• If gcd(a, m) = 1, an inverse exists and is unique modulo m.
• If gcd(a, m) ≠ 1, no modular inverse exists.

Example: 3 has an inverse mod 11 because gcd(3,11)=1. But 6 has no inverse mod 15 because gcd(6,15)=3.

How this calculator works

1) Normalize the input

Negative numbers are allowed for a. The calculator first maps a into the standard range 0 ... m-1 using:

a mod m = ((a % m) + m) % m

2) Apply the Extended Euclidean Algorithm

The Extended Euclidean Algorithm finds integers x and y such that:

a·x + m·y = gcd(a,m)

If gcd(a,m)=1, that equation becomes a·x + m·y = 1, so x is exactly the modular inverse (possibly after reducing x modulo m).

3) Return a positive representative

Inverses are often reported in the range 0 ... m-1. So the calculator outputs:

inverse = ((x % m) + m) % m

Worked example

Suppose we want the inverse of 17 modulo 3120:

• Check gcd(17,3120) = 1, so an inverse exists.
• Run Extended Euclid and solve 17x + 3120y = 1.
• The solution gives x = -367 (one valid value).
• Convert to positive form: -367 mod 3120 = 2753.

So the inverse is 2753. Verify: 17 × 2753 = 46801, and 46801 mod 3120 = 1.

Why modular inverses matter

Cryptography

RSA key generation and RSA decryption both rely on modular inverses. The private exponent is found by taking an inverse modulo Euler’s totient (or Carmichael function). Without fast inverse computation, practical public-key cryptography would be much harder.

Solving congruences

To solve equations like a·x ≡ b (mod m), multiply both sides by the inverse of a (when it exists):

x ≡ a⁻¹·b (mod m)

Chinese Remainder Theorem (CRT)

CRT implementations repeatedly require inverses while combining congruences. This is common in performance-oriented math libraries and competitive programming tasks.

Common mistakes to avoid

• Using m = 1 or m = 0: modular inverse is not meaningful here.
• Ignoring gcd: if gcd(a,m) ≠ 1, there is no inverse.
• Forgetting normalization: negative values should be reduced modulo m.
• Using floating-point arithmetic: inverses are integer-number-theory objects, not decimal approximations.

Quick FAQ

Can the inverse be negative?

Yes, mathematically many equivalent inverse values exist (differing by multiples of m). This calculator returns the standard non-negative representative.

Is the answer unique?

Unique modulo m. That means all valid inverses are congruent to each other mod m.

Does this work for very large integers?

Yes. This page uses JavaScript BigInt, so it can handle integers beyond normal 64-bit range, as long as your browser supports BigInt.

Final note

Modular inverse is a small concept with huge practical reach. Whether you are studying abstract algebra, writing cryptographic code, or solving coding challenges, knowing when inverses exist—and how to compute them quickly—is foundational. Use the calculator above to test values and inspect algorithm steps.