Modular Inverse Calculator

Find the modular multiplicative inverse a⁻¹ mod m using the extended Euclidean algorithm.

About Modular Inverse Calculator

The modular multiplicative inverse of a modulo m is an integer x such that a × x ≡ 1 (mod m). It exists if and only if gcd(a, m) = 1 (a and m are coprime). The extended Euclidean algorithm finds Bézout coefficients x, y with a×x + m×y = 1, and x mod m is the inverse.

Formula

Modular inverse

a × a⁻¹ ≡ 1 (mod m), exists iff gcd(a, m) = 1

a: Number
m: Modulus
a⁻¹: Modular inverse

Worked example

With the default values below, Modular Inverse Calculator returns Modular Inverse of 5. Change any input above and every figure here is recalculated in your browser.

Inputs used

a: 3
Modulus (m)minimum 2: 7

Results

Modular Inverse: 5
Verification: 3 × 5 mod 7 = 1

Step by step

1Check coprimality
2Extended Euclidean algorithm
3Result= 3⁻¹ mod 7 = 5
4Verify

Assumptions and limits

The result is derived only from the 2 inputs listed above. Anything not among them is not part of the calculation.
In particular, this calculator does not take inflation, tax, fees or charges or compounding frequency into account.
Figures are rounded for display to whole numbers, so totals built from several rounded parts can differ slightly from the unrounded arithmetic.

How these calculators are built and tested is described on the Methodology page. If a figure looks wrong, please report it.

Frequently Asked Questions

When does a modular inverse not exist?

The inverse of a mod m does not exist when a and m share a common factor greater than 1, i.e. gcd(a, m) ≠ 1. For example, 4 has no inverse mod 6 because gcd(4, 6) = 2.

What is the modular inverse used for?

It is essential in RSA encryption, solving linear congruences, the Chinese Remainder Theorem, and modular division. In RSA, the private key is essentially a modular inverse of the public exponent.