Modular Inverse Calculator

Find the modular inverse x of an integer a modulo m (a times x is congruent to 1 mod m) using the extended Euclidean algorithm, with an existence check via gcd and full working.

Input

Enter an integer a and a modulus m to find the modular inverse x of a modulo m, where a times x is congruent to 1 mod m, using the extended Euclidean algorithm.

Integer a

The integer to invert. Negative values are allowed.

Modulus m

An integer of 2 or more.

Result

Inverse of 3 modulo 11

Check: 3 times 4 leaves remainder 1 when divided by 11

gcd(a, m)

Inverse exists

Yes

Normalized a

Extended Euclidean algorithm

At each step the dividend is divided by the divisor to give a quotient and remainder. When the remainder reaches 0, the greatest common divisor is found.

Dividend	Divisor	Quotient	Remainder
3	11	0	3
11	3	3	2
3	2	1	1
2	1	2	0

Bezout coefficients

3 times 4 plus 11 times -1 equals 1

The modular inverse x is the integer for which a times x is congruent to 1 mod m. It exists only when the greatest common divisor of a and m is 1. The coefficient s, normalized into the range 0 to m minus 1, is the inverse.

Modular inverses appear in cryptography such as RSA, where the private exponent is found as the inverse of the public exponent modulo the value of Euler totient.

How it works

The modular inverse x is the integer for which a times x leaves a remainder of 1 when divided by m. In symbols, a times x is congruent to 1 mod m, with x between 0 and m minus 1.
An inverse exists only when a and m are coprime, that is when the greatest common divisor gcd(a, m) equals 1. If the gcd is not 1, no inverse exists.
The calculation uses the extended Euclidean algorithm, which finds gcd(a, m) together with coefficients s and t satisfying a s plus m t equals gcd.
When the gcd is 1, the coefficient s is the inverse. If it is negative, m is added to normalize it into the range 0 to m minus 1.
The input a is first reduced modulo m (into the range 0 to m minus 1) before the computation. Negative values of a are supported.
Modular inverses are used in RSA key generation. The private exponent d is found as the inverse of the public exponent e modulo the value of Euler totient.

Reviews

Tell us what you think of this calculator.