Với một số nguyên $a$, ta gọi nghịch đảo modulo $m$ [modular multiplicative inverse] của $a$ là $a^{-1}$ là số nguyên thoả mãn:
$a * a^{-1} \equiv 1 \; \pmod{m}$
Ta cần chú ý rằng không phải lúc nào $a^{-1}$ cũng tồn tại. Ví dụ, với $m = 4, a = 2$, ta không thể tìm được $a^{-1}$ thoả mãn đẳng thức trên.
Có thể chứng minh rằng $a^{-1}$ luôn luôn tồn tại nếu $gcd[a, m] = 1$.
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:
- Extended Euclid
- Tính a^b % c bằng chia để trị
- Phi hàm Euler
Extended Euclid
Như đã trình bày trong bài viết Số học 1, nếu $gcd[a, m] = 1$, ta luôn luôn tìm được 2 số nguyên x và y thoả mãn:
$a *x + m * y = 1$.
Vì ta đang làm việc trên modulo $m$, ta có thể bỏ $m * y$ và viết lại đẳng thức trên như sau:
$a * x \equiv 1 \pmod{m}$.
Do đó, $x$ chính là $a^{-1}$.
Cài đặt:
int x, y;
int g = extended_euclidean[a, m, x, y];
if [g != 1] cout