The modular inverse of a mod m is x where ax ≡ 1 (mod m). Exists iff gcd(a,m) = 1 (coprime). Found via Extended Euclidean Algorithm: ax + my = gcd(a,m). If gcd=1, then x mod m is the inverse. Critical in RSA encryption: d = e⁻¹ mod φ(n).
How to Use
Enter a and m:
- a: Number to invert
- m: Modulus
- Output: a⁻¹ mod m
Extended Euclidean
Compute gcd(a,m) while tracking coefficients x,y such that ax+my=gcd. If gcd=1, x mod m is the inverse.
Cryptography
RSA: choose e, compute d = e⁻¹ mod φ(n). d is the private key. Without efficient modular inverse, RSA key generation is impossible.
Step-by-Step Instructions
- 1Enter a.
- 2Enter modulus m.
- 3View inverse (if exists).
- 4See algorithm steps.
- 5Verify a × a⁻¹ ≡ 1 (mod m).