Modular Inverse
The modular inverse of a number a modulo n is a number x such that their product equals 1 (mod n). It's like division in modular arithmetic!
a × a⁻¹ ≡ 1 (mod n)
Key Insight: The modular inverse exists if and only if GCD(a, n) = 1. This is why the extended Euclidean algorithm is so important!
Inverse Calculator
Find the modular inverse of a number:
Enter values to find the modular inverse...
When Does an Inverse Exist?
A number a has an inverse mod n only when a and n are coprime (GCD = 1).
Inverse Exists
- 3⁻¹ mod 7 = 5 (since 3×5 = 15 ≡ 1)
- 7⁻¹ mod 26 = 15 (since 7×15 = 105 ≡ 1)
- 5⁻¹ mod 12 = 5 (since 5×5 = 25 ≡ 1)
No Inverse
- 4⁻¹ mod 8 = ∅ (GCD = 4)
- 6⁻¹ mod 9 = ∅ (GCD = 3)
- 10⁻¹ mod 15 = ∅ (GCD = 5)
Inverse Table
See which numbers have inverses for a given modulus:
Solving Linear Congruences
The modular inverse helps us solve equations of the form:
ax ≡ b (mod n)
If GCD(a, n) = 1, we can multiply both sides by a⁻¹ to get x ≡ a⁻¹b (mod n).
Congruence Solver
Enter values to solve the congruence...
Connection to RSA
In RSA: The decryption exponent d is the modular inverse of e mod φ(n). Finding d = e⁻¹ mod φ(n) is exactly what the extended Euclidean algorithm does!