Modular Multiplicative Inverse Calculator

Find x such that (a × x) ≡ 1 (mod m) using the Extended Euclidean Algorithm.

Enter Values

Find x such that (a × x) ≡ 1 (mod m). The inverse exists only when gcd(a, m) = 1.

Result

Modular Inverse of a (mod m)
4
(3 × 4) ≡ 1 (mod 11)
a 3
m (modulus) 11
gcd(a, m) 1
Inverse (x) 4
Verification 3 × 4 = 12 ≡ 1 (mod 11)

Extended Euclidean Algorithm Steps

(a × x) ≡ 1 (mod m)

What Is a Modular Multiplicative Inverse?

The modular multiplicative inverse of an integer a modulo m is an integer x such that the product a × x is congruent to 1 with respect to the modulus m. In mathematical notation: a × x ≡ 1 (mod m).

The modular inverse exists if and only if a and m are coprime, meaning their greatest common divisor (GCD) is 1. When it exists, the inverse is unique modulo m (meaning there is exactly one value of x in the range 0 to m-1).

Methods for Computing the Modular Inverse

Extended Euclidean Algorithm

The most common method. It finds integers x and y such that ax + my = gcd(a, m). When gcd = 1, x is the modular inverse.

ax + my = gcd(a, m) = 1

Fermat's Little Theorem

When m is prime, am-2 mod m gives the inverse. This follows from am-1 ≡ 1 (mod m).

a-1 ≡ am-2 (mod m)

Euler's Theorem

Generalization: aφ(m)-1 mod m, where φ is Euler's totient function. Works when gcd(a,m) = 1.

a-1 ≡ aφ(m)-1 (mod m)

When It Does Not Exist

If gcd(a, m) ≠ 1, then no modular inverse exists. For example, 2 has no inverse mod 4 since gcd(2,4) = 2.

gcd(a, m) ≠ 1 → no inverse

The Extended Euclidean Algorithm Explained

The Extended Euclidean Algorithm (EEA) is an extension of the standard Euclidean Algorithm for computing the GCD. While the standard algorithm finds gcd(a, m), the extended version also finds coefficients x and y such that ax + my = gcd(a, m).

How It Works

  1. Apply the Euclidean algorithm: repeatedly divide and take remainders until you reach 0.
  2. Back-substitute to express 1 as a linear combination of a and m.
  3. The coefficient of a (taken mod m) is the modular inverse.

Applications

Modular multiplicative inverses are essential in many areas:

  • RSA Cryptography: Computing the private key requires finding modular inverses.
  • Chinese Remainder Theorem: Solving systems of congruences uses modular inverses.
  • Modular Arithmetic: Division in modular arithmetic is defined as multiplication by the inverse.
  • Competitive Programming: Many problems require computing inverses modulo a prime.
  • Error-Correcting Codes: Reed-Solomon codes rely on arithmetic in finite fields using inverses.

Example Walkthrough

Find the inverse of 3 modulo 11:

  1. Apply EEA: 11 = 3 × 3 + 2, then 3 = 2 × 1 + 1, then 2 = 1 × 2 + 0.
  2. Back-substitute: 1 = 3 - 2 × 1 = 3 - (11 - 3 × 3) = 4 × 3 - 1 × 11.
  3. So x = 4, and indeed 3 × 4 = 12 ≡ 1 (mod 11).