## Nghịch đảo modulo
### Định nghĩa
Ở chương trình Toán phổ thông, nghịch đảo của một số nguyên $a$ có kí hiệu là $a^{-1}$ hay viết một cách dễ hiểu hơn là $\frac{1}{a}$, thỏa mãn:

                                                             $a \times a^{-1}$ = 1

Đối với nghịch đảo Modulo, ta cũng có khái niệm tương tự: Nghịch đảo modulo **$M$** của một số $a$ (kí hiệu là $a^{-1}$) là số nguyên thỏa mãn điều kiện:

                                                  $a \times a^{-1} \equiv 1 \pmod{M}$

Tuy vậy, $a^{-1}$ hay nghịch đảo modulo $M$ của $a$ không phải lúc nào cũng tồn tại mà chỉ xuất hiện khi và chỉ khi thỏa mãn được điều kiện:

                                                         $GCD(a, M) = 1$

Và để tìm được nghịch đảo modulo M của số $a$ bất kì, ta có thể sử dụng hai phương pháp sau: Giải thuật $Euclid$ mở rộng hoặc dựa trên định lý $Fermat$ nhỏ.

### Giải thuật $Euclid$ mở rộng

Theo cơ sở lý thuyết của giải thuật $Euclid$ mở rộng thì sẽ luôn luôn tồn tại các số nguyên $x, y$ thỏa mãn:

                                    $ax + by = d$   $\mid$   $d = GCD(a, b)$   $\forall$   $a, b$ $\in$ $N$

Giải thuật này được sử dụng phổ biến nhằm để tìm ra được cặp số nguyên $(x, y)$  $\in$ $N$ thỏa mãn phương trình trên và còn để dùng để tính nghịch đảo modulo. Áp dụng giải thuật này lên định nghĩa đã được phát biểu ở phần trên, ta được:

                                               $GCD(a, M) = 1$
                                          $\Rightarrow$ $a \times x + M \times y = 1$ & $M \times y$ chia hết cho $M$
                                          $\Rightarrow$ $a \times x \equiv 1 \pmod{M}$

Từ đây, ta có thể kết luận $x$ chính là $a^{-1}$. Tuy vậy, trong giải thuật $Euclid$ mở rộng, $x$ hay $a^{-1}$ có thể mang giá trị âm, nên ta sẽ cần điều chỉnh một chút để luôn được giá trị $a^{-1}$ luôn không âm. Code:

#include <bits/stdio.h>

using namespace std;

long long d; // d là UCLN của a, M
long long modulo_inverse(long long a, long long M)
{
    extended_euclid(a, M);
	  
    // a và M không nguyên tố cùng nhau, không tồn tại nghịch đảo modulo M của a.
    if (d != 1)
        return -1; 

    // Do x có thể âm, ta làm dương nó.
    return (x % M + M) % M; 
}

### Định lý $Fermat$ nhỏ

Dựa vào định lý $Fermat$ nhỏ, ta có được: Nếu $M$ là số nguyên tố và $a$ không chia hết cho $M$ thì $a^{M - 1} - 1$ sẽ chia hết cho $M$:

            $a^{M-1}\equiv 1 \ (\text{mod} \ M)$ hay nói cách khác: $a\times a^{M-2} \equiv 1 \ (\text{mod} \ M)$

Điều này cũng có nghĩa là nếu $M$ là số nguyên tố và $a$ không chia hết cho $M$ thì $a^{M - 2}$ là nghịch đảo modulo $M$ của $a$, cũng tương tự với $a^{M - 2}$ % $M$ là nghịch đảo modulo của $a$.

#include <bits/stdio.h>

using namespace std;

long long power_mod(long long a, long long b, long long M) // Tính a^b % M {
      if (b == 0)
           return 1;
      if (b == 1)
           return a;

      long long half = power_mod(a, b / 2, M) % M;
      if (b % 2 == 0)
           return (half * half) % M;
      else 
           return (((half * half) % M) * a) % M;
}

long long modulo_inverse(int a, int M){
      return power_mod(a, M – 2, M);
}

### Áp dụng

#### Bài toán : Tính $\frac{a}{b}$ % $c$

Để tính được phép tính ở trên, ta cần có một chút biến đổi nhỏ để đưa phép chia trên thành 1 phép nhân với mục đích lợi dụng nghịch đảo modulo tính được số dư:

- Tách $\frac{a}{b} \ \% \ c$ = $(a \times \frac{1}{b}) \ \% \ c$ = $(a \times b^{-1}) \ \% \ c$ với $b^{-1}$ là nghịch đảo modulo $c$ của $b$.
- Sau đó, ta sẽ áp dụng tính chất phân phối của phép nhân lên phép đồng dư thức. Ta sẽ được một phép nhân với nghịch đảo modulo.
* **Lưu ý**: Tùy vào giá trị của $c$ mà ta chọn cách tính nghịch đảo modulo hợp lí, phù hợp.

long long modulo_divide(long long a, long long b, long long c){
      long long inverse = modulo_inverse(b, c);
      return (a % c * inverse) % c;
}