# Modular Multiplicative Inverse

This tool computes x, the multiplicative inverse under modulo n of a,   ax\equiv1 (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.