# Modular Multiplicative Inverse

## 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)`.

`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