Multiplicative Inverse Modulo Calculator – Modular Arithmetic
Find the modular multiplicative inverse of a number.
How to Use
- Enter the number (a) for which you want to find the inverse
- Enter the modulus (n)
- Click calculate to find the multiplicative inverse
- The inverse exists only if gcd(a, n) = 1
What is a Multiplicative Inverse Modulo?
The multiplicative inverse of a number 'a' modulo 'n' is a number 'x' such that (a × x) ≡ 1 (mod n). In other words, when you multiply 'a' by its inverse 'x' and divide by 'n', the remainder is 1.
For example, the multiplicative inverse of 3 modulo 7 is 5, because 3 × 5 = 15 ≡ 1 (mod 7).
When Does the Inverse Exist?
The multiplicative inverse of 'a' modulo 'n' exists if and only if 'a' and 'n' are coprime, meaning their greatest common divisor (GCD) is 1.
- If gcd(a, n) = 1, the inverse exists and is unique modulo n
- If gcd(a, n) > 1, no inverse exists
- For prime modulus p, every non-zero number has an inverse
Extended Euclidean Algorithm
This calculator uses the Extended Euclidean Algorithm to find the multiplicative inverse. The algorithm finds integers x and y such that ax + ny = gcd(a, n). When gcd(a, n) = 1, x is the multiplicative inverse.
Applications
Modular multiplicative inverses are essential in many areas:
- RSA encryption and decryption
- Solving linear congruences
- Chinese Remainder Theorem
- Cryptographic protocols
- Error-correcting codes
Frequently Asked Questions
- Why doesn't my number have an inverse?
- A multiplicative inverse modulo n only exists when the number and n are coprime (their GCD is 1). If they share a common factor greater than 1, no inverse exists.
- How is this used in RSA encryption?
- In RSA, the private key d is the multiplicative inverse of the public exponent e modulo φ(n). This relationship allows decryption of messages encrypted with the public key.
- What if my number is negative?
- The calculator handles negative numbers by first converting them to their positive equivalent modulo n. For example, -3 mod 7 = 4, so finding the inverse of -3 mod 7 is the same as finding the inverse of 4 mod 7.
- Is the inverse always unique?
- The inverse is unique modulo n. While there are infinitely many numbers x satisfying (a × x) ≡ 1 (mod n), they all differ by multiples of n and are equivalent in modular arithmetic.