Modular Multiplicative Inverse¶
Definition¶
A modular multiplicative inverse of an integer
We will also denote
We should note that the modular inverse does not always exist. For example, let
In this article, we present two methods for finding the modular inverse in case it exists, and one method for finding the modular inverse for all numbers in linear time.
Finding the Modular Inverse using Extended Euclidean algorithm¶
Consider the following equation (with unknown
This is a Linear Diophantine equation in two variables.
As shown in the linked article, when
Now, if we take modulo
Thus, the modular inverse of
The implementation is as follows:
int x, y;
int g = extended_euclidean(a, m, x, y);
if (g != 1) {
cout << "No solution!";
}
else {
x = (x % m + m) % m;
cout << x << endl;
}
Notice that the way we modify x
.
The resulting x
from the extended Euclidean algorithm may be negative, so x % m
might also be negative, and we first have to add m
to make it positive.
Finding the Modular Inverse using Binary Exponentiation¶
Another method for finding modular inverse is to use Euler's theorem, which states that the following congruence is true if
If
Multiply both sides of the above equations by
- For an arbitrary (but coprime) modulus
- For a prime modulus
From these results, we can easily find the modular inverse using the binary exponentiation algorithm, which works in
Even though this method is easier to understand than the method described in previous paragraph, in the case when
Finding the modular inverse for prime moduli using Euclidean Division¶
Given a prime modulus
where
Note that this reasoning does not hold if
If the modulus is prime however, all
int inv(int a) {
return a <= 1 ? a : m - (long long)(m/a) * inv(m % a) % m;
}
The exact time complexity of the this recursion is not known. It's is somewhere between
Applying this formula, we can also precompute the modular inverse for every number in the range
inv[1] = 1;
for(int a = 2; a < m; ++a)
inv[a] = m - (long long)(m/a) * inv[m%a] % m;
Finding the modular inverse for array of numbers modulo ¶
Suppose we are given an array and we want to find modular inverse for all numbers in it (all of them are invertible). Instead of computing the inverse for every number, we can expand the fraction by the prefix product (excluding itself) and suffix product (excluding itself), and end up only computing a single inverse instead.
In the code we can just make a prefix product array (exclude itself, start from the identity element), compute the modular inverse for the product of all numbers and than multiply it by the prefix product and suffix product (exclude itself). The suffix product is computed by iterating from the back to the front.
std::vector<int> invs(const std::vector<int> &a, int m) {
int n = a.size();
if (n == 0) return {};
std::vector<int> b(n);
int v = 1;
for (int i = 0; i != n; ++i) {
b[i] = v;
v = static_cast<long long>(v) * a[i] % m;
}
int x, y;
extended_euclidean(v, m, x, y);
x = (x % m + m) % m;
for (int i = n - 1; i >= 0; --i) {
b[i] = static_cast<long long>(x) * b[i] % m;
x = static_cast<long long>(x) * a[i] % m;
}
return b;
}