numvana

Modular Inverse Calculator

Find the modular inverse of an integer — the value x such that a·x ≡ 1 (mod m) — using the extended Euclidean algorithm.

Modular inverse
4
Check
3 × 4 ≡ 1 (mod 11)

How it works

The modular inverse of a number a with respect to a modulus m is the integer x, between 0 and m−1, such that a×x leaves a remainder of 1 when divided by m — written a·x ≡ 1 (mod m). It's the modular analogue of a reciprocal: multiplying by it 'undoes' multiplying by a, within that modulus.

An inverse exists only when a and m are coprime — that is, gcd(a, m) = 1. This calculator finds it with the extended Euclidean algorithm, which computes gcd(a, m) alongside integer coefficients x and y satisfying a·x + m·y = gcd(a, m); when that gcd is 1, x (reduced into the 0..m−1 range) is exactly the modular inverse. When it isn't 1, no inverse exists and the calculator says so rather than returning a misleading number.

This is the companion calculation this site's Modular Exponentiation calculator deliberately leaves out — exponentiation uses square-and-multiply, a different algorithm entirely, and negative exponents (which mean 'raise to the inverse') need this extended Euclidean step first.

FAQ

Why doesn't every number have a modular inverse?

Because a·x mod m can only ever land on multiples of gcd(a, m) as x ranges over all integers. If gcd(a, m) isn't 1, the value 1 is never reachable no matter what x you pick — for example, 4 has no inverse mod 8, since every multiple of 4 mod 8 is either 0 or 4, never 1.

What's a practical use for a modular inverse?

It's a core building block of modular arithmetic and cryptography — RSA key generation, for instance, finds a private exponent that's the modular inverse of the public exponent with respect to a totient value. It's also how 'division' is defined in modular arithmetic, since there's no direct division operator — dividing by a mod m means multiplying by a's modular inverse instead.

Related calculators