Nguồn: e-maxx
Người dịch: Nguyễn Thành Trung (RR)
Xét số nguyên dương . Xét các số nguyên trên modulo (từ 0 đến ).
Với một số nguyên , ta gọi nghịch đảo modulo (modular multiplicative inverse) của là là số nguyên thoả mãn:
Ta cần chú ý rằng không phải lúc nào cũng tồn tại. Ví dụ, với , ta không thể tìm được thoả mãn đẳng thức trên.
Có thể chứng minh rằng luôn luôn tồn tại nếu .
Trong bài viết này, mình sẽ trình bày 2 cách khác nhau để tìm nghịch đảo modulo, dựa trên các kiến thức đã được trình bày ở các bài viết trên VNOI:
Như đã trình bày trong bài viết Số học 1, nếu , ta luôn luôn tìm được 2 số nguyên x và y thoả mãn:
.
Vì ta đang làm việc trên modulo , ta có thể bỏ và viết lại đẳng thức trên như sau:
.
Do đó, chính là .
Cài đặt:
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;
}
Khi , theo định lý Euler, ta có:
.
Với Phi hàm Euler đã được giải thích ở bài viết Số học 4.
Trong trường hợp là số nguyên tố, , nên ta có:
.
Nhân cả 2 vế với , ta được:
Như vậy, ta có thể dùng thuật toán Tính a^b % c bằng chia để trị để tính nghịch đảo modulo với độ phức tạp .
Trong trường hợp là số nguyên tố, ta cũng có thể tính tất cả nghịch đảo modulo của toàn bộ với độ phức tạp như sau:
r[1] = 1;
for(int i = 2; i < m; ++i)
r[i] = (m - (m/i) * r[m%i] % m) % m;
Chứng minh:
Nhân cả 2 vế với nghịch đảo modulo của và nghịch đảo modulo của :