![[7 ngày Lý Thuyết Số cơ bản]Ngày 3 - Đồng dư, nghịch đảo modulo và định lý số dư Trung Hoa1. Đồng dưGiả sử a và b là các...](https://img5.medioq.com/023/196/122237918540231964.jpg)
18/04/2025
[7 ngày Lý Thuyết Số cơ bản]
Ngày 3 - Đồng dư, nghịch đảo modulo và định lý số dư Trung Hoa
1. Đồng dư
Giả sử a và b là các số nguyên, và m là một số nguyên dương. Ta viết a ≡ b (mod m) nếu m chia hết cho b − a. Biểu thức a ≡ b (mod m) được gọi là một đồng dư, và được đọc là “a đồng dư với b theo mô-đun m”. Số nguyên m được gọi là mô-đun.
2. Giảm mô-đun
Giả sử ta chia a và b cho m, thu được các thương nguyên và các dư, trong đó các dư nằm trong khoảng từ 0 đến m − 1. Cụ thể, a = q1.m + r1 và b = q2.m + r2, với 0 ≤ r1 ≤ m − 1 và 0 ≤ r2 ≤ m − 1. Khi đó, không khó để thấy rằng a ≡ b (mod m) nếu và chỉ nếu r1 = r2. Ta sử dụng ký hiệu a mod m (không có dấu ngoặc) để biểu thị dư khi a chia cho m, tức là giá trị r1 ở trên. Do đó, a ≡ b (mod m) nếu và chỉ nếu a mod m = b mod m. Nếu ta thay a bằng a mod m, ta nói rằng a được giảm theo mô-đun m. Quá trình này được
gọi là giảm mô-đun.
3. Ta định nghĩa số học mô-đun m: Zm là tập hợp {0, . . . , m − 1}, trong đây có hai phép toán + (phép cộng) và · (phép nhân). Phép cộng và phép nhân trong Zm hoạt động giống hệt như phép cộng và phép nhân thông thường, ngoại trừ việc kết quả được giảm
theo mô-đun m.
Ví dụ: Giả sử ta muốn tính 11 + 13 trong Z16. Với các số nguyên, ta có 11 + 13 = 24. Sau đó, ta giảm 24 theo mô-đun 16 như đã mô tả ở trên: 24 = 1 × 16 + 8, nên 24 mod 16 = 8, và do đó 11 + 13 = 8 trong Z16.
4. Nghịch đảo modulo (modular inverse) của một số a theo mô-đun m là một số x sao cho: a · x ≡ 1 (mod m).
Nói cách khác, x là nghịch đảo nhân của a theo mô-đun m, và điều kiện để x tồn tại là gcd(a, m) = 1 (tức là a và m phải nguyên tố cùng nhau).
Ví dụ: Nghịch đảo modulo của 4 theo mô-đun 11 là 3 vì 4 · 3 ≡ 1 (mod 11).
Nghịch đảo modulo có thể được tìm thông qua thuật toán Euclide mở rộng, được trình bày trong bài viết dưới comment. Thuật toán Euclid mở rộng giúp tìm x và y sao cho a.x + m.y = gcd(a, m). Nếu gcd(a, m) = 1, thì x chính là nghịch đảo modulo của a theo m. Trong trường hợp tìm được x âm, ta có thể phải xử lý thêm để đảm bảo kết quả nằm trong Zm.
-a mod m = (m - a) mod m
5. Định lý số dư Trung Hoa
Giả sử m1, . . . , mr là các số nguyên dương đôi một nguyên tố cùng nhau, và giả sử a1, . . . , ar là các số nguyên. Khi đó, hệ r đồng dư x ≡ ai (mod mi) (1 ≤ i ≤ r) có một nghiệm duy nhất theo mô-đun M = m1 × · · · × mr, được cho bởi công thức:
x = tổng ai.Mi.yi mod M với (1 ≤ i ≤ r)
trong đó, Mi = M/Mi, yi là nghịch đảo modulo của Mi trong mô-đun mi
![[7 ngày Lý Thuyết Số cơ bản]Ngày 2 - UCLN, BCNNƯớc chung lớn nhất của hai số a,b là số nguyên lớn nhất mà cả a và b cùng...](https://img4.medioq.com/823/196/122233174358231964.jpg)
![[7 ngày Lý Thuyết Số cơ bản]Ngày 1- Số nguyên tốSố nguyên tố là số tự nhiên lớn hơn 1 và chỉ chia hết cho 1 và chính nó,...](https://img3.medioq.com/423/196/122232633854231964.jpg)
