NUMBER THEORYArithmeticMathematics Calculator
⁻¹

Multiplicative Inverse Modulo: a×a⁻¹ ≡ 1 (mod m)

a⁻¹ mod m satisfies a×a⁻¹ ≡ 1 (mod m). Exists iff gcd(a,m)=1. Extended Euclidean Algorithm finds it. Fermat: a⁻¹ ≡ a^(m-2) when m is prime.

Concept Fundamentals
a×a⁻¹≡1
a⁻¹
Exists iff
gcd(a,m)=1
Algorithm
EEA
a^(m-2) if prime
Fermat

Did our AI summary help? Let us know.

a×a⁻¹ ≡ 1 (mod m). Exists iff gcd(a,m)=1. Extended Euclidean: ax+my=1 ⇒ x ≡ a⁻¹ (mod m). Fermat: prime m ⇒ a⁻¹ ≡ a^(m-2) (mod m).

Key quantities
a×a⁻¹≡1
a⁻¹
Key relation
Exists iff
gcd(a,m)=1
Key relation
Algorithm
EEA
Key relation
a^(m-2) if prime
Fermat
Key relation

Ready to run the numbers?

Why: Modular inverse is essential for division in mod m: a/b = a×b⁻¹. RSA decryption uses (c^d) mod n where d is inverse of e mod φ(n). Linear congruences.

How: Extended Euclidean: find x,y with ax+my=gcd(a,m). If gcd=1, x is a⁻¹ mod m. Fermat: a⁻¹ ≡ a^(m-2) when m prime. Inverse exists iff gcd(a,m)=1.

a×a⁻¹ ≡ 1 (mod m). Exists iff gcd(a,m)=1.Extended Euclidean: ax+my=1 ⇒ x ≡ a⁻¹ (mod m).
Sources:Khan Academy CryptographyNIST

Run the calculator when you are ready.

Find Modular InverseEnter a and m

Enter Values

mod_inverse.sh
CALCULATED
$ mod_inverse --a=7 --m=26
a⁻¹ mod m
15
gcd(a,m)
1
Verification
7×15 ≡ 1
Status
Exists ✓
Multiplicative Inverse Modulo
7⁻¹ mod 26 = 15
Verification: 7 × 15 ≡ 1 (mod 26)
numbervibe.com
Share:

Values

Status

📐 Step-by-Step Breakdown

PROBLEM
a × x ≡ 1 (mod m)
7 × x ≡ 1 (mod 26)
CHECK
gcd(a, m)
1
Inverse exists?
Yes
RESULT
a⁻¹ mod m
15
Verification: 7 × 15 ≡ 1 (mod 26)

For educational and informational purposes only. Verify with a qualified professional.

🧮 Fascinating Math Facts

⁻¹

a×a⁻¹ ≡ 1 (mod m)

— Definition

📐

Exists iff gcd(a,m)=1

— Coprime

📋 Key Takeaways

  • • a × x ≡ 1 (mod m) means x is the multiplicative inverse of a modulo m
  • • Inverse exists iff gcd(a, m) = 1 (a and m are coprime)
  • • Extended Euclidean Algorithm finds the inverse efficiently
  • • Used in cryptography (RSA, Diffie-Hellman), linear congruences, CRT

💡 Did You Know?

🔐RSA encryption uses modular inverses to compute the private key from the public keySource: Cryptography
📐For prime m, every 1 ≤ a < m has an inverse (Fermat: a^(m-2) mod m)Source: Fermat's Little Theorem
⏰Clock arithmetic: 7 hours + 7 hours = 2 (mod 12). 7⁻¹ mod 12 = 7Source: Modular arithmetic
📜Euler's totient φ(m) counts integers coprime to m; φ(p)=p-1 for prime pSource: Euler's Theorem
🧮Extended Euclidean Algorithm: finds x,y such that ax + my = gcd(a,m)Source: Number theory
✓Verification: a × a⁻¹ mod m should equal 1Source: Definition

📖 How It Works

Enter a and m. The calculator uses the Extended Euclidean Algorithm to find x such that a×x ≡ 1 (mod m). If gcd(a,m) ≠ 1, no inverse exists. Advanced mode with "Show Extended Euclidean steps" displays the full algorithm trace.

📝 Worked Example: 7 mod 26

Find x: 7×x ≡ 1 (mod 26)

gcd(7, 26) = 1 ✓

Extended GCD: 7×15 + 26×(-4) = 1

So: 7×15 ≡ 1 (mod 26) → inverse is 15

Verification: 7 × 15 = 105 ≡ 1 (mod 26) ✓

🚀 Real-World Applications

🔐 RSA

Private key d = e⁻¹ mod φ(n).

📜 Affine Cipher

Decryption key inverse mod 26.

📐 Linear Congruences

Solve ax ≡ b by x ≡ b×a⁻¹.

🌍 CRT

Chinese Remainder Theorem construction.

🔢 Division mod m

a/b ≡ a×b⁻¹ mod m.

💻 Error Correction

Reed-Solomon codes.

⚠️ Common Mistakes to Avoid

  • Assuming inverse exists: Only when gcd(a,m)=1.
  • Modulus 1: When m=1, inverse of any a is 0 (special case).
  • Not reducing: Inverse is unique mod m; reduce to [0, m).
  • Zero: 0 has no multiplicative inverse.

🎯 Expert Tips

💡 Prime Modulus

When m is prime, use Fermat: a⁻¹ = a^(m-2) mod m.

💡 Solving ax ≡ b

Multiply both sides by a⁻¹: x ≡ b × a⁻¹ (mod m).

💡 Applications

Cryptography, CRT, division in modular arithmetic.

💡 Extended Euclidean

Enable in advanced mode to see the full algorithm trace.

📊 Reference Table

ConditionInverse
gcd(a,m)=1Exists, unique mod m
gcd(a,m)≠1Does not exist
m primeAll 1..m-1 have inverses

📐 Quick Reference

a×x≡1
Definition
gcd=1
Existence
EEA
Algorithm
a^(p-2)
Fermat (prime)

🎓 Practice Problems

3 mod 11 → Answer: 4
5 mod 12 → Answer: 5
9 mod 10 → Answer: 9
2 mod 8 → No inverse (gcd=2)

❓ FAQ

When does the multiplicative inverse exist?

Only when gcd(a, m) = 1. If a and m share a common factor, no inverse exists.

How is this used in cryptography?

RSA uses modular inverses to derive the private key. The inverse of e mod φ(n) gives d.

What is the Extended Euclidean Algorithm?

An algorithm that finds integers x, y such that ax + my = gcd(a,m). When gcd=1, x is the inverse of a mod m.

What is Fermat's Little Theorem?

For prime p and a not divisible by p: a^(p-1) ≡ 1 (mod p). So a⁻¹ = a^(p-2) mod p.

Can 0 have an inverse?

No. 0 × x ≡ 0 (mod m) for any x, so 0 never equals 1 mod m.

How do I verify?

Check a × a⁻¹ mod m = 1.

Difference from Inverse Modulo?

Same concept. This calculator offers extended Euclidean step display.

📌 Summary

The multiplicative inverse a⁻¹ mod m satisfies a×a⁻¹ ≡ 1 (mod m). It exists iff gcd(a,m)=1. The Extended Euclidean Algorithm finds it. Used in RSA, affine ciphers, and CRT.

✅ Verification Tip

Always verify: a × (inverse) mod m = 1. If not, either the inverse is wrong or gcd(a,m) ≠ 1.

🔗 Next Steps

Try the Inverse Modulo Calculator, Extended Euclidean Algorithm for Bézout coefficients, or Chinese Remainder Theorem for congruence systems.

⚠️ Disclaimer: For educational use. Verify results for cryptographic applications with established libraries.

👈 START HERE
⬅️Jump in and explore the concept!
AI

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.

Mathematics

Inverse Modulo Calculator

Find the modular multiplicative inverse a^(-1) mod m using the Extended Euclidean Algorithm. Requires gcd(a,m)=1. Step-by-step solutions for cryptography...

Mathematics

Chinese 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...

Mathematics

Relatively Prime Calculator

Check if two or more integers are relatively prime (coprime). GCD = 1 means no common factors. Euler totient, Euclidean algorithm, coprime pairs.

Mathematics

Power 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...

Mathematics

Consecutive 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....

Mathematics