Mathwords logoMathwords

Modular Inverse — Definition, Formula & Examples

The modular inverse of an integer aa modulo mm is the integer xx such that multiplying aa by xx gives a remainder of 1 when divided by mm. It exists only when aa and mm share no common factors other than 1.

Given integers aa and mm with gcd⁡(a,m)=1\gcd(a, m) = 1, the modular inverse of aa modulo mm is the unique integer xx in {1,2,…,m−1}\{1, 2, \ldots, m-1\} satisfying ax≡1(modm)ax \equiv 1 \pmod{m}.

Key Formula

a⋅x≡1(modm)a \cdot x \equiv 1 \pmod{m}
Where:
  • aa = The integer whose inverse you want to find
  • xx = The modular inverse of a modulo m
  • mm = The modulus

How It Works

Finding a modular inverse is like solving a division problem in modular arithmetic — since you cannot directly divide, you multiply by the inverse instead. To find it, you can test values of xx from 1 to m−1m-1, use the Extended Euclidean Algorithm, or apply Euler's theorem: aϕ(m)−1 mod ma^{\phi(m)-1} \bmod m, where ϕ(m)\phi(m) is Euler's totient function. For a prime modulus pp, this simplifies to ap−2 mod pa^{p-2} \bmod p by Fermat's Little Theorem. The inverse exists if and only if gcd⁡(a,m)=1\gcd(a, m) = 1.

Worked Example

Problem: Find the modular inverse of 3 modulo 7.
Step 1: You need an integer xx such that 3x≡1(mod7)3x \equiv 1 \pmod{7}. Since 7 is prime, you can use Fermat's Little Theorem: x=37−2=35 mod 7x = 3^{7-2} = 3^5 \bmod 7.
35=2433^5 = 243
Step 2: Reduce 243 modulo 7.
243=34×7+5  ⟹  243 mod 7=5243 = 34 \times 7 + 5 \implies 243 \bmod 7 = 5
Step 3: Verify: multiply 3 by 5 and check the remainder.
3×5=15≡1(mod7)✓3 \times 5 = 15 \equiv 1 \pmod{7} \checkmark
Answer: The modular inverse of 3 modulo 7 is 55.

Why It Matters

Modular inverses are essential in cryptography — the RSA encryption algorithm relies on computing them with very large primes. They also appear in competition math problems and in solving systems of linear congruences using the Chinese Remainder Theorem.

Common Mistakes

Mistake: Trying to find a modular inverse when gcd⁡(a,m)≠1\gcd(a, m) \neq 1 (e.g., the inverse of 4 modulo 8).
Correction: The modular inverse only exists when aa and mm are coprime. Always check gcd⁡(a,m)=1\gcd(a, m) = 1 first.