In modular arithmetic, dividing by a means multiplying by its inverse. Computing inverses is a daily task in cryptography – for example finding the private exponent d in RSA.
How to use the Multiplicative Inverse Modulo Calculator
- a
- m (modulus)
Everything is calculated in your browser, so results appear instantly and nothing you type is sent to a server.
How it works
The extended Euclidean algorithm finds the Bézout coefficients of a and m. If gcd(a, m) = 1, the coefficient of a, reduced modulo m, is the inverse.
Formula
a·x ≡ 1 (mod m) ⇔ a·x + m·y = 1 for some integer y
Worked example
Inputs — a: 17; m (modulus): 3,120.
Results — Inverse x = 2753; Check = 17 × 2753 = 46801 ≡ 1 (mod 3120); Extended Euclidean algorithm = Extended Euclidean algorithm:
17 = 0 × 3120 + 17
3120 = 183 × 17 + 9
17 = 1 × 9 + 8
9 = 1 × 8 + 1
8 = 8 × 1 + 0
Back-substitution gives 17 × (-367) + 3120 × (2) = 1, so x ≡ 2753 (mod 3120).
Key terms
- Bézout coefficients
- The integers x and y in ax + my = gcd(a, m).
Frequently asked questions
What is the inverse of 17 mod 3120?
2753 – the classic RSA example.
Why must a and m be coprime?
Otherwise every multiple of a shares a factor with m and can never be 1 more than a multiple of m.
Is the inverse unique?
Yes, modulo m.
What is Bézout's identity?
For any a, m there are integers x, y with ax + my = gcd(a, m).