Modular Inverse: a⁻¹ mod m
The modular inverse of a mod m is x such that ax ≡ 1 (mod m). Exists iff gcd(a,m)=1. Found via Extended Euclidean Algorithm. Essential for RSA and Chinese Remainder Theorem.
Did our AI summary help? Let us know.
Inverse exists iff gcd(a,m)=1 (a and m coprime). RSA: d = e⁻¹ mod φ(n) for decryption. Fermat: a^(p-1) ≡ 1 (mod p) → a⁻¹ = a^(p-2) mod p.
Ready to run the numbers?
Why: Modular inverse lets you 'divide' in modular arithmetic. Division by a mod m = multiply by a⁻¹. RSA decryption uses this. CRT requires inverses for each modulus.
How: Use Extended Euclidean Algorithm: find x,y with ax+my=gcd(a,m). When gcd=1, x mod m is the inverse. Or: a^(φ(m)-1) mod m when m is prime (Fermat).
Run the calculator when you are ready.
Enter Values
i×a mod m (inverse when =1)
Values
📐 Step-by-Step Breakdown
For educational and informational purposes only. Verify with a qualified professional.
🧮 Fascinating Math Facts
RSA decryption uses modular inverse of e mod φ(n).
Inverse exists iff gcd(a,m)=1.
📋 Key Takeaways
- • a^(-1) mod m exists iff gcd(a, m) = 1 (a and m coprime)
- • Extended Euclidean Algorithm finds x such that a×x ≡ 1 (mod m)
- • Used in RSA decryption, affine ciphers, solving linear congruences
- • Fermat: if m is prime, a^(-1) ≡ a^(m-2) mod m
💡 Did You Know?
📖 How It Works
The extended Euclidean algorithm finds integers x, y such that ax + my = gcd(a,m). When gcd(a,m) = 1, we get ax ≡ 1 (mod m), so x is the modular inverse. We reduce x to the range [0, m). The algorithm repeatedly applies division: r₁ = q·r₂ + r, updating coefficients s, t until r₂ = 0.
📝 Worked Example: 3 mod 11
Find x: 3×x ≡ 1 (mod 11)
Check: gcd(3, 11) = 1 ✓
Extended GCD: 3×4 + 11×(-1) = 1
So: 3×4 ≡ 1 (mod 11) → inverse is 4
Verification: 3 × 4 = 12 ≡ 1 (mod 11) ✓
🚀 Real-World Applications
🔐 RSA Decryption
Private key d is inverse of e mod φ(n).
📜 Affine Cipher
Decryption needs inverse of key mod 26.
📐 Linear Congruences
Solve ax ≡ b mod m by multiplying by a⁻¹.
🌍 Chinese Remainder Theorem
CRT construction uses modular inverses.
🔢 Division mod m
a ÷ b ≡ a × b⁻¹ mod m.
💻 Error Correction
Reed-Solomon and similar codes.
⚠️ Common Mistakes to Avoid
- Assuming inverse always exists: Only when gcd(a, m) = 1.
- Forgetting to reduce: Inverse is unique mod m; reduce to [0, m).
- Negative a: Reduce a mod m first: a = ((a % m) + m) % m.
- Modulus ≤ 1: No meaningful inverse when m = 1.
🎯 Expert Tips
💡 Prime Modulus
Use a^(-1) ≡ a^(m-2) mod m (Fermat) for speed when m is prime.
💡 Coprime Check
Always verify gcd(a,m)=1 first.
💡 Negative a
Reduce a mod m first: a = ((a%m)+m)%m.
💡 Applications
RSA, affine cipher, linear congruence ax≡b mod m.
📊 Reference Table
| Method | When |
|---|---|
| Extended Euclidean | General case, gcd(a,m)=1 |
| Fermat a^(m-2) | m prime, a not divisible by m |
| Euler a^(φ(m)-1) | gcd(a,m)=1, φ = totient |
📐 Quick Reference
🎓 Practice Problems
❓ FAQ
What is modular inverse?
x such that a×x ≡ 1 (mod m). Like 1/a in normal arithmetic.
When does it exist?
Only when gcd(a, m) = 1. a and m must be coprime.
How to find it?
Extended Euclidean algorithm or Fermat's theorem when m is prime.
RSA use?
Decryption exponent d is inverse of e mod φ(n).
Solve ax ≡ b mod m?
Multiply both sides by a^(-1): x ≡ b×a^(-1) mod m.
Negative numbers?
Reduce to [0, m) first. -5 mod 12 = 7.
Verify?
Check a × a⁻¹ mod m = 1.
📌 Summary
The modular inverse a^(-1) mod m satisfies a×a^(-1) ≡ 1 (mod m). It exists iff gcd(a,m)=1. The Extended Euclidean Algorithm finds it. Used in RSA, affine ciphers, and solving linear congruences.
✅ Verification Tip
Always verify: a × (inverse) mod m should equal 1. If not, the inverse is wrong or gcd(a,m) ≠ 1.
🔗 Next Steps
Try the Multiplicative Inverse Modulo Calculator for extended steps, the Extended Euclidean Algorithm for Bézout coefficients, or the Chinese Remainder Theorem for congruence systems.
⚠️ Disclaimer: For educational use. Verify cryptographic calculations with established libraries.
Related Calculators
Extended Euclidean Algorithm Calculator
Find gcd(a,b) and Bézout coefficients x, y such that ax + by = gcd(a,b). Step-by-step division table. Modular inverse, linear Diophantine equations.
MathematicsMultiplicative Inverse Modulo Calculator
Find the multiplicative inverse of a modulo m: a×x ≡ 1 (mod m). Uses the Extended Euclidean Algorithm with step-by-step trace. Applications in cryptography (RSA, Diffie-Hellman), linear congruences, and Chinese Remainder Theorem. Verify with Fermat's Little Theorem for prime moduli.
MathematicsChinese Remainder Theorem Calculator
Solve systems of congruence equations x ≡ a_i (mod m_i) using the Chinese Remainder Theorem. Step-by-step solution with multiple moduli, modular inverse, and...
MathematicsPower Mod Calculator
Compute a^b mod m (modular exponentiation) using the fast square-and-multiply algorithm. Essential for cryptography (RSA, Diffie-Hellman), number theory, and...
MathematicsConsecutive Integers Calculator
Find n consecutive integers that sum to a target, or compute sum and product of consecutive integers. Supports even and odd consecutive sequences....
MathematicsPerfect Square Calculator
Check if a number is a perfect square, find its square root, and explore nearby squares. Includes digit pattern analysis, prime factorization verification...
Mathematics