Multiplicative Inverse Modulo Calculator
Find modular multiplicative inverse using Extended Euclidean Algorithm with step-by-step solutions
Calculate Multiplicative Inverse Modulo
The number whose multiplicative inverse we want to find
The modulus (must be positive)
Modular Multiplicative Inverse Result
Why? The multiplicative inverse of a modulo m exists if and only if gcd(a, m) = 1. Since gcd(NaN, 0) = 0, the numbers are not coprime and the inverse doesn't exist.
Example Calculations
Basic Example
Find inverse of 3 modulo 7
Prime Modulus
Prime modulus ensures inverse exists
Larger Numbers
Modular inverse with larger numbers
No Inverse Case
Example where inverse doesn't exist
Key Concepts
Definition
x is the multiplicative inverse of a mod m if a × x ≡ 1 (mod m)
Existence Condition
Inverse exists ⟺ gcd(a, m) = 1 (coprime)
Prime Modulus
If m is prime, all non-zero a < m have inverses
Extended GCD
Most efficient algorithm for finding modular inverses
Algorithm Comparison
Extended Euclidean
O(log min(a,m)) - Very efficient
Brute Force
O(m) - Educational only
Fermat's Little Theorem
a^(p-2) mod p when p is prime
Understanding Modular Multiplicative Inverse
What is Modular Multiplicative Inverse?
The modular multiplicative inverse of a modulo m is a number x such that:
a x x ≡ 1 (mod m)This means when you multiply a and x, the remainder when divided by m is 1.
When Does It Exist?
- Coprime condition: gcd(a, m) = 1
- Prime modulus: If m is prime, inverse exists for all 1 ≤ a < m
- Composite modulus: Only for numbers coprime to m
Extended Euclidean Algorithm
Step 1: Find GCD
Use Euclidean algorithm to find gcd(a, m)
Step 2: Bézout's Identity
Find x, y such that ax + my = gcd(a, m)
Step 3: Extract Solution
If gcd = 1, then x is our multiplicative inverse
Worked Example
Find inverse of 3 modulo 7:
7 = 2 x 3 + 1
3 = 3 x 1 + 0
gcd(3, 7) = 1 ✓
Working backwards:
1 = 7 - 2 x 3
So: 3 x (-2) + 7 x 1 = 1
Therefore: 3 x 5 ≡ 1 (mod 7)
Answer: 5
Applications
Cryptography
RSA encryption, Diffie-Hellman key exchange
Linear Congruences
Solving equations ax ≡ b (mod m)
Number Theory
Modular arithmetic, group theory
Computer Science
Hash functions, pseudo-random generators