Inverse Modulo Calculator
Calculate modular additive and multiplicative inverses using the Extended Euclidean Algorithm
Calculate Modular Inverse
The number for which to find the inverse
The modulus (must be positive)
Please enter valid integers for both number and modulus.
Example Calculations
Multiplicative Inverse Example
Problem: Find multiplicative inverse of 3 mod 11
Check: gcd(3, 11) = 1 ✓ (coprime)
Extended Euclidean:
11 = 3 × 3 + 2
3 = 2 × 1 + 1
1 = 3 - 2 × 1 = 3 - (11 - 3 × 3) = 4 × 3 - 11
Answer: 3⁻¹ ≡ 4 (mod 11)
Verification: 3 × 4 = 12 ≡ 1 (mod 11) ✓
Additive Inverse Example
Problem: Find additive inverse of 7 mod 12
Solution: We need x where 7 + x ≡ 0 (mod 12)
Formula: x ≡ -7 (mod 12)
Calculation: -7 + 12 = 5
Answer: Additive inverse is 5
Verification: 7 + 5 = 12 ≡ 0 (mod 12) ✓
Key Properties
Multiplicative Inverse
Exists only if gcd(a, m) = 1
a × x ≡ 1 (mod m)
Additive Inverse
Always exists for any a and m
a + x ≡ 0 (mod m)
Extended Euclidean
Finds gcd and Bézout coefficients
ax + by = gcd(a, b)
Applications
RSA Cryptography
Solving Modular Equations
Chinese Remainder Theorem
Number Theory Problems
Elliptic Curve Cryptography
Quick Tips
Check coprimality first for multiplicative inverse
Additive inverse always exists
Use Extended Euclidean for efficient computation
Result is unique in range [0, m-1]
Understanding Modular Inverses
What are Modular Inverses?
A modular inverse is a number that, when combined with another number using a specific operation, produces the identity element under modular arithmetic. There are two types: additive and multiplicative inverses.
Multiplicative Inverse
- •Finds x where a × x ≡ 1 (mod m)
- •Exists only when gcd(a, m) = 1
- •Essential in RSA cryptography
Extended Euclidean Algorithm
The Extended Euclidean Algorithm not only finds the GCD of two numbers but also finds the coefficients (Bézout coefficients) that satisfy the linear Diophantine equation.
ax + by = gcd(a, b)
If gcd(a, m) = 1, then ax ≡ 1 (mod m)
Additive Inverse
- •Finds x where a + x ≡ 0 (mod m)
- •Always exists: x ≡ -a (mod m)
- •Simple formula: x = ((-a % m) + m) % m
Cryptographic Applications
Modular multiplicative inverses are fundamental in modern cryptography:
- •RSA Encryption: Private key is multiplicative inverse of public exponent
- •Elliptic Curves: Point operations require modular division
- •Digital Signatures: Signing process uses multiplicative inverses
Mathematical Properties
Key Theorems
Bézout's Identity: For integers a, b, there exist integers x, y such that ax + by = gcd(a, b)
Coprimality Condition: Multiplicative inverse of a mod m exists if and only if gcd(a, m) = 1
Uniqueness: If the multiplicative inverse exists, it is unique in the range [0, m-1]