Modular Inverse Calculator (Extended)
Find the modular multiplicative inverse using the extended Euclidean algorithm.
Find a^(-1) mod m
Algorithm Steps
| i | q | r | s | t |
|---|---|---|---|---|
| 0 | - | 17 | 1 | 0 |
| 1 | 0 | 43 | 0 | 1 |
| 2 | 2 | 17 | 1 | 0 |
| 3 | 1 | 9 | -2 | 1 |
| 4 | 1 | 8 | 3 | -1 |
| 5 | 8 | 1 | -5 | 2 |
Existence Condition
The modular inverse exists if and only if:
gcd(a, m) = 1
When it exists, it satisfies:
a * a^(-1) ≡ 1 (mod m)
Modular Inverse
17^(-1) ≡ 38 (mod 43)
GCD(a, m)
1
Inverse
38
Verification
17 × 38 mod 43 = 1
Correct: equals 1
Alternative Method
Using Euler's theorem:
phi(43) = 42
17^(42-1) mod 43 = 38
Matches!
Applications
- RSA decryption
- Solving linear congruences
- Division in modular arithmetic
- Chinese Remainder Theorem