Modular Inverse Calculator
Find the modular multiplicative inverse a⁻¹ mod m using the extended Euclidean algorithm.
Inputs
The number whose inverse you want (must be coprime with m).
The modulus (must be ≥ 2 and coprime with a).
Modular Inverse
5
Verification
3 × 5 mod 7 = 1
Step by step
Check coprimality
gcd(3, 7) = 1 ✓
Extended Euclidean algorithm
Find x: 3 × x ≡ 1 (mod 7)
Result
= 3⁻¹ mod 7 = 5
Verify
3 × 5 = 15 ≡ 1 (mod 7)
How it works
The modular multiplicative inverse of a modulo m is an integer x such that a × x ≡ 1 (mod m). It exists if and only if gcd(a, m) = 1 (a and m are coprime). The extended Euclidean algorithm finds Bézout coefficients x, y with a×x + m×y = 1, and x mod m is the inverse.
Formula
Modular inverse
a × a⁻¹ ≡ 1 (mod m), exists iff gcd(a, m) = 1
- a
- Number
- m
- Modulus
- a⁻¹
- Modular inverse
Frequently Asked Questions
When does a modular inverse not exist?
The inverse of a mod m does not exist when a and m share a common factor greater than 1, i.e. gcd(a, m) ≠ 1. For example, 4 has no inverse mod 6 because gcd(4, 6) = 2.
What is the modular inverse used for?
It is essential in RSA encryption, solving linear congruences, the Chinese Remainder Theorem, and modular division. In RSA, the private key is essentially a modular inverse of the public exponent.
You might also need
- Extended Euclidean Algorithm CalculatorCommonly used together
- Chinese Remainder Theorem CalculatorCommonly used together
- Euclidean Algorithm CalculatorCommonly used together
- Euler Totient CalculatorCommonly used together
- Fibonacci CalculatorAlso in Number Theory
- Composite Number CheckerAlso in Number Theory