Modular Multiplicative Inverse

This tool computes x, the multiplicative inverse under modulo n of a,   ax`\equiv`1 (mod n).

Modular Multiplicative Inverse : definition and existence

a and n are two integers.
The Modular Multiplicative Inverse of a modulo n is the integer x such that,

`a * x \equiv 1 (mod n)`

x is sometimes denoted `a^(-1)`.

Equivalently, there is an integer k such as,

`1 - a * x = k*n`

`a * x + k*n = 1`

According to Bezout Theorem, k exists if and only if a and n are coprime numbers.

In conclusion, the Modular Multiplicative Inverse exists if and only if a and n are coprime. It is then unique (modulo n) i.e. there is only one inverse between 1 and n but we can find an infinity of integers satisying the modular inverse equation simply by adding n multiples to x because for every integer p,

`a * (x+p*n) \equiv 1 (mod n)`

How to calculate the Modular Multiplicative Inverse ?

The Modular Multiplicative Inverse can be calculated by using the extended Euclid algorithm.
Using this algorithm, if a and n are coprime, we can find coefficients u and v two integers such as,

`u*a + v*n = 1`

By applying modulo n to the members of this equality,

`u*a \equiv 1 (mod n)`

We conclude that the modular inverse is the coefficient of a in the extended Euclidean algorithm applied to integers a and n.

See also

Coprime numbers test
GCD Calculator
Bezout Theorem and Extended Euclid Algorithm
Arithmetic Calculators
Equation and Inequation Calculators
Mathematical Calculators

---