The modular multiplicative inverse of a number n modulo p is a number m such that
n-1≡m (mod p).
Since this is equivalent to
1/mn≡ 1 (mod p),
it can be simplified to
mn≡ 1 (mod p).
We can sometimes find an m where this congruence is true. The m that is selected, however, is generally the smallest m possible.
For example:
3-1≡m (mod 11)
gives us
3m≡ 1 (mod 11).
The smallest m that fits this congruence is 4; therefore, the modular multiplicative inverse is 4.
If m and n are coprime then the modular multiplicative inverse always exists. It can easily be found using the extended Euclidean algorithm by inputting gcd(n, m). The result is the multiplier to the first argument. The extended Euclidean algorithm is an extension to the Euclidean algorithm for finding the greatest common divisor (GCD) of a and b: it also finds the integers x and y in Bezouts identity The extended Euclidean algorithm is particularly useful when a and b are coprime, since x is...
Feeds |
Contact