Modular Multiplicative Inverse
Modular Multiplicative Inverse : definition and existencea 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.