Understanding Modular Multiplicative Inverse
The modular multiplicative inverse of an integer a modulo m is an integer x such that a · x ≡ 1 (mod m). In other words, when you multiply a by x and divide by m, the remainder is 1. This concept is fundamental in number theory and has critical applications in cryptography.
Methods for Finding Modular Inverse
Extended Euclidean Algorithm
The most efficient general method. It finds x and y such that ax + my = gcd(a, m). If gcd = 1, then x is the inverse.
Fermat's Little Theorem
When m is prime: a-1 ≡ am-2 (mod m). Only works for prime modulus.
Euler's Theorem
General version: a-1 ≡ aφ(m)-1 (mod m) where φ is Euler's totient.
Brute Force
Try all values x from 1 to m-1 until ax mod m = 1. Only practical for small m.
When Does the Inverse Exist?
The modular inverse of a modulo m exists if and only if gcd(a, m) = 1, meaning a and m are coprime (share no common factors other than 1). If gcd(a, m) > 1, then no inverse exists because the equation ax ≡ 1 (mod m) has no solution.
Properties of Modular Inverse
- If a-1 exists mod m, it is unique in the range [1, m-1].
- (a · b)-1 ≡ a-1 · b-1 (mod m).
- (a-1)-1 ≡ a (mod m).
- 1-1 ≡ 1 (mod m) for any m.
- (m-1)-1 ≡ m-1 (mod m) since (m-1)² = m² - 2m + 1 ≡ 1.
Applications
- RSA encryption: Computing decryption keys requires modular inverse.
- Solving linear congruences: ax ≡ b (mod m) becomes x ≡ a-1b (mod m).
- Chinese Remainder Theorem computations.
- Cryptographic hash functions and digital signatures.
- Error-correcting codes (Reed-Solomon codes).