LÝ THUYẾT ĐỒNG DƯ

1. Khái niệm cơ bản

Trong toán học, đồng dư mô tả việc hai số chia cho cùng một số (gọi là modulo) thì có cùng số dư.

ký hiệu: ~a ≡ b~ (mod ~m~) Nghĩa là: a và b chia cho m có cùng số dư. Hay nói cách khác: ~m ∣ ( a − b )~ (m chia hết cho a - b)

2. Ví dụ minh hoạ

• ~17 ≡ 5~ (mod 12)

Vì ~17 ÷ 12 = 1~ dư 5, ~5 ÷ 12~ dư 5

• ~25 ≡ 1~ (mod 12)

Vì ~25 ÷ 12 = 2~ dư 1 và ~1 ÷ 12 = 0~ dư 1 ~→~ cùng số dư.

• ~14 ≡ 2~ (mod 4)

Vì cả 14 và 2 đều chia 4 dư 2

3. Tính chất của đồng dư

Nếu ~A ≡ B~ (mod M) thì:

1. Cộng

(A + B) % M = ((A % M) + (B % M)) % M

2. Trừ

(A - B) % M = ((A % M) - (B % M)) % M

3. Nhân

(A * B) % M = ((A % M) * (B % M)) % M

4. Chia

(A / B) % M = ((A % M) * (~B^{-1}~ % M)) % M

Ý nghĩa: Ta có thể "rút gọn" số lớn về số nhỏ cùng dư để tính toán dễ dàng hơn.

4. Lý giải công thức

Ví dụ: ~(a + b) \bmod m~

• Giả sử ~a = qm + r, \; b = pm + s~ với ~r, s~ là số dư.
• Khi đó: $$ a + b = (q + p).m + (r + s) $$
• Chia cho ~m~, ta thấy số dư chỉ phụ thuộc vào ~r + s~.

Kết luận: $$ (a + b) \bmod m = \big((a \bmod m) + (b \bmod m)\big) \bmod m $$

5. Các dạng thường gặp trong lập trình thi đấu

Rút gọn số lớn bằng modulo

Thường dùng với ~m = 10^9 + 7~ để tránh tràn số.

Công thức: $$ (a + b) \bmod m = \big((a \bmod m) + (b \bmod m)\big) \bmod m $$

Tính lũy thừa đồng dư

Dùng trong bài toán số mũ lớn:
$$ a^b \bmod m $$

Giải bằng lũy thừa nhị phân (fast exponentiation).

So sánh chia hết / đồng dư

Kiểm tra điều kiện:

(a - b) % m == 0

Ứng dụng trong thuật toán nâng cao

• Hệ phương trình đồng dư (Chinese Êmainder Therem)
• Mật mã RSA