# Đồng dư thức
## 1. Định nghĩa

Đồng dư thức là khái niệm trong toán học mô tả việc hai số có cùng số dư khi chia cho một số khác. Trong lập trình, ký hiệu phép toán này là $\%$. Cụ thể, cho hai số nguyên $a$ và $b$ cùng với số nguyên dương $m$, ta nói $a$ **đồng dư với** $b$ theo mô-đun $m$ nếu $a$ và $b$ có cùng số dư khi chia cho $m$, ký hiệu:

$$
a \equiv b \pmod{m}
$$

Nói cách khác, $a \% m = b \% m$.

### Các phép toán đồng dư cơ bản

1. **Phép cộng:**
$$
(a + c) \% m = (a\%m+b\%m) \% m
$$

2. **Phép trừ:**
$$
(a - c) \% m = (a\%m-b\%m) \% m
$$

3. **Phép nhân:**
$$
(a \cdot c) \% m = (a\%m\cdot b\%m) \% m
$$

## 2. Ứng dụng

Đồng dư thức giúp kiểm tra số dư trong nhiều tình huống thực tế và có ứng dụng rộng rãi trong lập trình, mã hóa, và lý thuyết số.

Áp dụng vào các bài khi số quá lớn cần in ra phần dư khi chia cho 1 số

## 3. Áp dụng

### Bài toán: $a^n$ % $m$ $(1<n<10^{5}; m<10^5)$
- Vì $a^n$ với $a$ là số bất kì trong khoảng từ $2$ đến $10^5$ thì $a^{10^5}$ luôn vượt quá giới hạn số nguyên của c++, việc tính $a^{10^5}$ sau đó mới chia lấy phần dư cho $m$ sẽ bị tràn số
- Vậy ta sẽ dùng một trong các phép đồng dư là phép nhân để tránh tình trạng tràn số

 int sol(int a, int n, int m) {
    int result = 1;
    a = a % m;
    for(int i=1; i<=n; ++i){
        result=(result%m * a%m) %m;
    }
    return result%m;
}