Trong toán học, phép toán “mod” hay “modulo” đóng vai trò quan trọng, đặc biệt trong các lĩnh vực như số học, mật mã học và khoa học máy tính. Bài viết này sẽ đi sâu vào khái niệm “mod là gì”, các tính chất và ứng dụng thực tế của nó.
Định Nghĩa Phép Modulo
Phép Lấy Phần Dư
Cho hai số nguyên (a) và (b), với (b neq 0), ký hiệu (a bmod b) là số dư của phép chia (a) cho (b).
Ví dụ:
- (30 bmod 7 = 2)
- (10 bmod 2 = 0)
- (-12 bmod 5 = 3) (Trong một số ngôn ngữ lập trình, kết quả có thể là -2. Tuy nhiên, trong toán học, ta thường ưu tiên số dư dương.)
alt: Ví dụ minh họa phép chia 30 cho 7, thương là 4, số dư là 2, thể hiện rõ ràng ý nghĩa của phép modulo.
Một cách chính xác, xét phép chia Euclid của (a) cho (b):
(a = bq + r)
Trong đó:
- (q in mathbb{Z}) (q là thương số nguyên)
- (0 leq r < |b|) (r là số dư, luôn không âm và nhỏ hơn giá trị tuyệt đối của b)
Đồng Dư
Cho số nguyên (n > 1) và hai số nguyên (a) và (b), ta ký hiệu (a equiv b pmod n) khi (a) và (b) có cùng số dư khi chia cho (n). Ta đọc là “(a) đồng dư với (b) modulo (n)”.
Ví dụ:
(12 equiv 7 equiv 2 pmod 5)
(-3 equiv 2 pmod 5)
Như vậy, (a equiv b pmod n iff a bmod n = b bmod n).
Ký hiệu (bar{a}_n) là tập hợp tất cả các số đồng dư với (a) trong modulo (n):
[bar{a}_n = {x mid x equiv a pmod n }]
Ta có vành (mathbb{Z}/n) là tập hợp tất cả các (bar{a}_n):
[mathbb{Z}/n = {bar{a}_n mid a in mathbb{Z}}]
Ví dụ:
(bar{8}_5 = bar{3}_5 = {dots,-7, -2, 3, 8, 13,dots}\
mathbb{Z}/5 = {bar{0}_5, bar{1}_5, bar{2}_5, bar{3}_5, bar{4}_5})
alt: Biểu diễn vành Z/5, minh họa các lớp tương đương đồng dư modulo 5, thể hiện tính tuần hoàn của các số dư.
Các Phép Toán Trên Vành Modulo và Tính Chất
Phần này xét phép cộng và phép nhân trên vành modulo.
[bar{a}_n + bar{b}_n = overline{a + b}_n]
[bar{a}_n – bar{b}_n = overline{a – b}_n]
[bar{a}_n bar{b}_n = overline{a b}_n]
Ví dụ: (bar{6}_{10} + bar{8}_{10} = overline{6 + 8}_{10} = overline{14}_{10} = bar{4}_{10}). Điều này có nghĩa là: “số chia 10 dư 6” cộng với “số chia 10 dư 8” sẽ cho kết quả là “số chia 10 dư 4”.
Ta cũng có thể sử dụng ký hiệu đồng dư: (6 + 8 equiv 14 equiv 4 pmod{10})
Dấu (equiv) có tính chất tương tự như dấu (=):
- (a equiv a pmod n) (Tính phản xạ)
- (a equiv b pmod n iff b equiv a pmod n) (Tính đối xứng)
- Nếu (a equiv b pmod n) và (b equiv c pmod n) thì (a equiv c pmod n) (Tính bắc cầu)
Cho (a, b, k in mathbb{Z}), nếu (a equiv b pmod n) thì ta có các tính chất sau:
- (-a equiv -b pmod n)
- (a + k equiv b + k pmod n)
- (ka equiv kb pmod n)
- (a^k equiv b^k pmod n)
- Tổng quát, (p(a) equiv p(b) pmod n), với (p) là đa thức có hệ số nguyên.
Ngược lại:
- (a + k equiv b + k pmod n iff a equiv b pmod n)
- Nếu (ka equiv kb pmod n) và (k) nguyên tố cùng nhau với (n) thì (a equiv b pmod n)
Cho (a_1 equiv b_1 pmod n) và (a_2 equiv b_2 pmod n), ta có:
- (a_1 + a_2 equiv b_1 + b_2 pmod n)
- (a_1 – a_2 equiv b_1 – b_2 pmod n)
- (a_1 a_2 equiv b_1 b_2 pmod n)
alt: Minh họa trực quan về các phép toán cộng, trừ, nhân trong số học modulo, giúp dễ hình dung cách các số “cuộn lại” khi đạt đến modulo.
Ứng Dụng Của Toán Đồng Dư
Một ứng dụng quan trọng của toán đồng dư là kiểm tra tính chia hết của một số. Ví dụ, chứng minh rằng “Một số chia hết cho 3 khi và chỉ khi tổng các chữ số của số đó chia hết cho 3”.
Xét số (A) có (n) chữ số trong hệ thập phân: (a_0, a_1, a_2,dots,a_{n-1}), ta có:
[A = a_0 + 10 a_1 + 10^2 a2 + dots + 10^{n-1} a{n-1}]
Theo đề bài, (A) chia hết cho 3, nghĩa là: (A equiv 0 pmod 3)
Tương đương với:
[a_0 + 10 a_1 + 10^2 a2 + dots + 10^{n-1} a{n-1} equiv 0 pmod 3]
Vì (10 equiv 1 pmod 3) nên ta có thể thay 10 bằng 1 trong biểu thức trên:
[a_0 + 1 a_1 + 1^2 a2 + dots + 1^{n-1} a{n-1} equiv 0 pmod 3]
[iff a_0 + a_1 + a2 + dots + a{n-1} equiv 0 pmod 3]
Chứng minh hoàn tất. Tương tự, ta có thể chứng minh các số chia hết cho 9 sẽ có tổng các chữ số chia hết cho 9.
Toán đồng dư còn có nhiều ứng dụng khác trong các lĩnh vực:
- Mật mã học: Các thuật toán mã hóa hiện đại sử dụng rộng rãi phép modulo để đảm bảo tính bảo mật.
- Khoa học máy tính: Trong băm (hashing), phép modulo được sử dụng để ánh xạ dữ liệu vào các vị trí trong bảng băm.
- Lý thuyết số: Toán đồng dư là nền tảng cho nhiều kết quả quan trọng trong lý thuyết số.
