Giả sử ta có là hai số nguyên tố cùng nhau (). Khi này, tồn tại một số nguyên thoả mãn:
Số nguyên được gọi là nghịch đảo modulo (modular multiplicative inverse) của , kí hiệu là hay .
Với nghịch đảo modulo, ta có thể tính được giá trị của biểu thức .
Ghi chú: bài viết giả sử . Nếu , ta có thể gán lại giá trị của thành và giá trị của vẫn không đổi.
Ta có một số phương pháp để tính nghịch đảo modulo:
Đây là một trong những phương pháp đơn giản nhất để tính nghịch đảo modulo. Theo định lí Euler, ta có:
Với là phi hàm Euler của . Từ đây, ta suy ra:
Vậy, nghịch đảo modulo sẽ bằng .
Nếu là số nguyên tố, ta có thể áp dụng định lí Fermat nhỏ, từ đó tính được .
int modInv(int a, int m){ // giả sử a, m nguyên tố cùng nhau
int p = phi(m); // hàm `phi(n)` tính phi hàm Euler của n
int x = Pow(a, p - 1, m); // hàm `Pow(a, b, c)` tính a^b mod c
return x;
}
Việc tính phi hàm Euler với độ phức tạp , cộng thêm với việc tính luỹ thừa với độ phức tạp , làm độ phức tạp của thuật toán bằng . Nếu là số nguyên tố thì việc tính phi hàm Euler sẽ nhanh hơn (phi hàm Euler của một số nguyên số là ), và độ phức tạp của thuật toán sẽ bằng .
Nhìn lại biểu thức tìm nghịch đảo modulo, ta thấy các giá trị của đồng dư thức có thể được viết thành đẳng thức với là một số nguyên bất kì. Ta viết lại đẳng thức này thành phương trình .
Phương trình là một phương trình Diophantine tuyến tính hai ẩn. Phương trình chỉ có nghiệm khi hai số và nguyên tố cùng nhau. Điều kiện này khớp với điều kiện để có nghịch đảo modulo.
int modInv(int a, int m){
int x, y;
d = extEuclid(a, m, x, y); // hàm euclid mở rộng ở bài Thuật toán Euclid
if (d != 1) return -1; // không tồn tại nghịch đảo modulo
x = (x % m + m) % m;
return x; // nghịch đảo modulo
}
Độ phức tạp của thuật toán bằng .
Giả sử là số nguyên tố. Khi này, ta có thể tìm được nghịch đảo modulo của các số trong khoảng từ bằng công thức
Với là số cần tìm nghịch đảo modulo, là các số có giá trị sao cho ().
Với , ta có:
Nguyên nhân phải là số nguyên tố là bởi như đã nói ở trên: để tìm nghịch đảo modulo của với modulo thì phải nguyên tố cùng nhau. Mặc dù ta có thể đảm bảo với nguyên tố cùng nhau, nhưng chưa chắc ta có thể đảm bảo và cũng nguyên tố cùng nhau.
Khi duyệt từ , các giá trị đã được tính trước do .
int inv[N];
void findInv(int m){
inv[1] = 1;
for(int i = 2; i < m; ++i){
inv[i] = m - 1ll * (m / i) * inv[m % i] % m;
}
}
Độ phức tạp của thuật toán này bằng .
Để tính nghịch đảo modulo của một mảng, ta có thể tính bằng cách tìm nghịch đảo modulo của từng phần tử một (độ phức tạp ) hoặc tính nhanh nghịch đảo modulo trong đoạn rồi tìm phần tử tương ứng (độ phức tạp ). Thay vì thế, ta chỉ cần thực hiện một lần tính nghịch đảo modulo của tích tất cả các phần tử. Khi tìm nghịch đảo của một phần tử, ta chỉ cần nhân nó với các phần tử còn lại trong mảng.
vector<int> arrInv (vector<int> &arr, int m){
int n = arr.size();
int v = 1;
vector<int> inv(n, 0);
for(int i = 0; i < n; ++i){
inv[i] = v;
v = (1ll * v * arr[i]) % m;
}
v = modInv(v, m);
for(int i = n - 1; i >= 0; --i){
inv[i] = (1ll * inv[i] * v) % m;
v = (1ll * v * arr[i]) % m;
}
return inv;
}
Độ phức tạp của thuật toán bằng với là kích thước mảng.
Ta cũng có thể làm điều tương tự để tính nghịch đảo modulo của giai thừa đầu tiên: .
vector<int> facInv (int n, int m){
int v = 1;
for(int x = 2; x <= n; ++x){
v = (1ll * v * x) % m;
}
vector<int> inv(n + 1, 1);
inv[n] = modInv(v, m);
for(int i = n; i >= 1; --i){
inv[i - 1] = (1ll * inv[i] * i) % m;
}
return inv;
}
Độ phức tạp của thuật toán này cũng bằng .