Multiplicative Inverse Modulo Calculator

Enter an integer a and a modulus m to find a⁻¹, the multiplicative inverse of a modulo m, using the Extended Euclidean Algorithm.

Quick Facts

Definition
a · a⁻¹ ≡ 1 (mod m)
a⁻¹ is the integer that "undoes" multiplication by a, under modulus m.
Existence condition
gcd(a, m) = 1
An inverse exists only when a and m are coprime.
Method
Extended Euclidean Algorithm
Finds integers x, y with a·x + m·y = gcd(a, m).
Reported range
0 ≤ a⁻¹ < m
The inverse is always reduced to a single representative mod m.

Your Results

Calculated
Multiplicative Inverse (a⁻¹ mod m)
-
Solves a · a⁻¹ ≡ 1 (mod m)
GCD(a, m)
-
Must equal 1 for an inverse to exist
Verification
-
a × a⁻¹ mod m
Bézout Coefficients
-
x, y such that a·x + m·y = gcd(a, m)

Ready

Enter an integer a and a modulus m (m ≥ 2), then press Calculate.

Formula and Method for the Multiplicative Inverse Modulo

The multiplicative inverse of an integer a modulo m is the integer a⁻¹, chosen from {0, 1, ..., m-1}, that satisfies a · a⁻¹ ≡ 1 (mod m). In other words, when a is multiplied by its inverse and the result divided by m, the remainder is 1. This only works for whole-number ("modular") arithmetic — it is a different concept from the ordinary reciprocal 1/a. A modular inverse exists precisely when a and m share no common factor other than 1, i.e. when gcd(a, m) = 1.

How the calculation works

This calculator uses the Extended Euclidean Algorithm. Starting from a and m, the algorithm repeatedly applies the division step of the ordinary Euclidean algorithm (for finding gcd), but also tracks two running coefficients so that at every stage it can express the current remainder as a linear combination of a and m. It terminates with integers x and y satisfying a·x + m·y = gcd(a, m). When gcd(a, m) = 1, this equation becomes a·x + m·y = 1, and reducing both sides modulo m gives a·x ≡ 1 (mod m) — so x, reduced into the range 0 to m-1, is exactly the modular inverse a⁻¹. The pair (x, y) are called the Bézout coefficients.

Common mistakes

  • Assuming an inverse always exists: if gcd(a, m) ≠ 1 (for example a = 4, m = 8), there is no integer that satisfies a·a⁻¹ ≡ 1 (mod m). The calculator reports this instead of a false answer.
  • Confusing modular inverse with ordinary division: a⁻¹ mod m is not 1/a; it is the specific integer in {0, ..., m-1} that makes a·a⁻¹ leave remainder 1 when divided by m.
  • Forgetting to reduce the result: the Extended Euclidean Algorithm can return a coefficient x outside the range 0 to m-1 (including negative values); it must be normalized with x mod m before it is reported as the inverse.

Real-world applications

  • Cryptography: RSA key generation computes the private exponent d as the modular inverse of the public exponent e modulo φ(n); Diffie-Hellman and elliptic-curve schemes use modular inverses for point arithmetic.
  • Solving linear congruences: an equation of the form a·x ≡ b (mod m) is solved by multiplying both sides by a⁻¹ mod m, giving x ≡ a⁻¹·b (mod m).
  • Chinese Remainder Theorem: combining solutions across several moduli (used in fast modular arithmetic and hashing) requires computing a modular inverse for each modulus.
  • Error-correcting codes and checksums: some coding schemes use modular inverses over finite fields to decode or verify data.

Frequently Asked Questions

What is a multiplicative inverse modulo m?
The multiplicative inverse of a modulo m is the integer a⁻¹, taken from {0, 1, ..., m-1}, such that a × a⁻¹ ≡ 1 (mod m). For example, the inverse of 3 modulo 11 is 4, because 3 × 4 = 12, and 12 mod 11 = 1.
When does a multiplicative inverse modulo m exist?
An inverse of a modulo m exists if and only if gcd(a, m) = 1, meaning a and m are coprime (share no common factor other than 1). If gcd(a, m) is greater than 1, no integer a⁻¹ can satisfy a × a⁻¹ ≡ 1 (mod m).
How does the Extended Euclidean Algorithm find the inverse?
The Extended Euclidean Algorithm finds integers x and y such that a·x + m·y = gcd(a, m). When gcd(a, m) = 1, this reduces to a·x ≡ 1 (mod m), so x — reduced into the range 0 to m-1 — is the modular inverse.
Where is the modular multiplicative inverse used?
Modular inverses are central to RSA and other cryptographic algorithms (computing the private key from the public exponent), to solving linear congruences of the form ax ≡ b (mod m), and to the Chinese Remainder Theorem used in computer arithmetic and hashing.

Related calculators