Math · Modular arithmetic
Modular inverse calculator.
Find x so that a times x leaves remainder 1 when divided by m. Shows the Euclidean steps, the Bezout line and a check, or explains why no inverse exists.
Inputs
Inverse
Enter a and m.
What is a modular inverse?
The modular inverse of a modulo m is the number x, from 0 to m - 1, for which (a x x) mod m = 1. It exists exactly when gcd(a, m) = 1, that is, when a and m are coprime. Python states the same condition for pow(base, -1, mod): the base must be relatively prime to the modulus, and pow(38, -1, mod=97) returns 23, because 23 x 38 = 874 = 9 x 97 + 1 (Python documentation).
How it is found. The Euclidean algorithm (Euclid, Elements VII.2) computes the gcd by repeated division. Running it in extended form also gives whole numbers x and y with a x x + m x y = 1, so x is the inverse modulo m. Worked examples. The inverse of 3 mod 11 is 4 (3 x 4 = 12 = 11 + 1). The inverse of 17 mod 3,120 is 2,753. 14 has no inverse mod 21 because gcd(14, 21) = 7.
Negative a. A negative a is first reduced into the range 0 to m - 1: -3 mod 11 = 8, whose inverse is 7.
Frequently asked questions
How do you find the modular inverse of a number?
Run the extended Euclidean algorithm on a and m. If the gcd is 1, the coefficient of a in a x + m y = 1, reduced mod m, is the inverse.
When does a modular inverse not exist?
When gcd(a, m) is greater than 1. For example 14 has no inverse mod 21 because they share the factor 7.
What is the inverse of 3 mod 11?
4, because 3 x 4 = 12 and 12 mod 11 = 1.
What is 17^-1 mod 3120?
2,753. Check: 17 x 2,753 = 46,801 = 15 x 3,120 + 1.
Does the modulus have to be prime?
No. Any modulus of 2 or more works as long as a and m are coprime. A prime modulus guarantees every non-zero a has an inverse.
Sources
Checked
The Euclidean algorithm is from Euclid, Elements Book VII; the coprime condition and the pow(38, -1, 97) = 23 example are from the Python documentation. Computed with exact BigInt arithmetic in your browser. Runs entirely in your browser. Nothing you type is sent or stored.
For learning
For learning and homework checking. Do not use a browser page to generate cryptographic keys.