Số học đồng dư là gì: phép chia lấy dư qua đồng hồ và ngày trong tuần

Số học đồng dư là số học chỉ quan tâm đến phần dư của phép chia. Hai số gọi là đồng dư theo môđun n khi chia cho n có cùng số dư, ví dụ 14 và 2 đồng dư theo môđun 12 vì cùng dư 2. Chiếc đồng hồ treo tường là ví dụ quen nhất: 9 giờ cộng 5 tiếng là 2 giờ, không phải 14 giờ, vì kim đồng hồ tự "chia cho 12 lấy dư".

Đồng dư là gì: ký hiệu và cách đọc

Ta viết a ≡ b (mod n), đọc là "a đồng dư với b theo môđun n", khi a và b chia cho n có cùng phần dư. Nói cách khác, hiệu a − b chia hết cho n. Ví dụ:

• 17 ≡ 5 (mod 12), vì 17 − 5 = 12.
• 100 ≡ 2 (mod 7), vì 100 = 14 × 7 + 2.
• −3 ≡ 4 (mod 7), vì −3 − 4 = −7 chia hết cho 7.

Ký hiệu ba gạch ≡ do Carl Friedrich Gauss đưa ra trong cuốn Disquisitiones Arithmeticae (Khảo cứu số học) năm 1801, khi ông mới 24 tuổi. Ý tưởng tính theo phần dư thì có từ lâu trước đó, nhưng Gauss biến nó thành một công cụ có quy tắc rõ ràng, giống như phép tính trên số thường.

Đồng hồ và ngày trong tuần: đồng dư hằng ngày

Đồng hồ 12 giờ là số học môđun 12. Bây giờ 9 giờ, 5 tiếng nữa là mấy giờ? 9 + 5 = 14 ≡ 2 (mod 12), nên 2 giờ. Bây giờ 3 giờ, 7 tiếng trước là mấy giờ? 3 − 7 = −4 ≡ 8 (mod 12), nên 8 giờ. Đồng hồ 24 giờ ở nhà ga, sân bay là môđun 24.

Tuần lễ là môđun 7. Đánh số Chủ nhật là 0, thứ Hai là 1, đến thứ Bảy là 6. Nếu hôm nay thứ Hai, 100 ngày nữa là thứ mấy? 100 chia 7 dư 2, nên tiến thêm hai thứ: thứ Tư. Một năm thường có 365 ngày, 365 chia 7 dư 1, nên sinh nhật năm sau rơi vào thứ liền sau thứ của năm nay; qua ngày 29/2 của năm nhuận thì nhảy hai thứ.

Cộng, trừ, nhân theo môđun: được phép rút gọn giữa chừng

Điều làm số học đồng dư mạnh là: muốn biết phần dư của một tổng, hiệu hay tích, chỉ cần lấy phần dư của từng số rồi tính. Ví dụ phần dư của 1.234 × 5.678 khi chia cho 9: 1.234 chia 9 dư 1 (vì 1 + 2 + 3 + 4 = 10, chia 9 dư 1), 5.678 chia 9 dư 8 (5 + 6 + 7 + 8 = 26, dư 8). Tích các phần dư là 8, vậy tích lớn chia 9 cũng dư 8. Không cần nhân ra 7.006.652.

Mẹo này là nền của phép thử số 9 người xưa dùng để kiểm phép nhân.

Tìm chữ số tận cùng của luỹ thừa lớn

Chữ số tận cùng của 7 mũ 2026 là gì? Chữ số tận cùng là phần dư khi chia cho 10. Các luỹ thừa của 7 theo môđun 10: 7, 49 → 9, 343 → 3, 2.401 → 1, rồi lặp lại 7, 9, 3, 1. Chu kỳ dài 4. 2026 chia 4 dư 2, nên 7 mũ 2026 có tận cùng giống 7 mũ 2, tức là 9. Một con số hàng nghìn chữ số mà biết ngay chữ số cuối chỉ bằng một phép chia.

Còn phép chia thì sao: chỗ đồng dư khác số thường

Cộng, trừ, nhân đều "an toàn" theo môđun. Phép chia thì không. Ví dụ 2 × 3 = 6 và 2 × 8 = 16 ≡ 6 (mod 10). Nếu được tuỳ tiện "giản ước số 2", ta sẽ có 3 ≡ 8 (mod 10), sai. Lý do: 2 và 10 có ước chung là 2.

Quy tắc đúng: chỉ được chia cho một số theo môđun n khi số đó và n nguyên tố cùng nhau (ƯCLN bằng 1). Khi ấy số đó có "nghịch đảo": một số mà nhân với nó cho ra 1. Ví dụ theo môđun 7, nghịch đảo của 3 là 5, vì 3 × 5 = 15 ≡ 1 (mod 7). "Chia cho 3" theo môđun 7 chính là "nhân với 5". Cách tìm nghịch đảo với số lớn là thuật toán Euclid mở rộng.

Khi môđun là số nguyên tố p, mọi số khác 0 đều có nghịch đảo, và ta làm đủ bốn phép tính như số thường. Đó là lý do mật mã học và mã sửa lỗi ưa dùng môđun nguyên tố. Năm 1640, Pierre de Fermat phát hiện thêm một tính chất: nếu p nguyên tố và a không chia hết cho p thì a mũ (p − 1) ≡ 1 (mod p). Ví dụ 3 mũ 6 = 729 = 104 × 7 + 1. Định lý nhỏ Fermat này về sau thành nền móng của hệ mã hoá RSA.

Phép chia lấy dư số âm: bẫy của người lập trình

Trong toán học, phần dư khi chia cho n luôn nằm từ 0 đến n − 1. Vậy −7 chia 3 dư bao nhiêu? Viết −7 = (−3) × 3 + 2, phần dư là 2. Nhưng các ngôn ngữ lập trình không thống nhất:

Nhóm C, Java, JavaScript cắt thương về phía 0 (−7 : 3 = −2,33… cắt thành −2), nên phần dư mang dấu số bị chia: −7 − (−2 × 3) = −1. Python và Excel làm tròn thương xuống (thành −3), nên phần dư cùng dấu số chia. Lỗi này hay gặp khi viết chương trình tính "thứ mấy của ngày trước đó": lùi 10 ngày từ thứ Ba bằng JavaScript cho ra số âm, không ứng với thứ nào. Cách chữa an toàn: lấy ((a % n) + n) % n.

Đồng dư ở khắp nơi trong công nghệ

• Chữ số kiểm tra: mã vạch, số thẻ ngân hàng, ISBN, IBAN đều thêm một chữ số được tính sao cho tổng có trọng số đồng dư với 0 theo môđun 10, 11 hoặc 97. Gõ sai một số là lệch phần dư, máy phát hiện ngay.
• Bảng băm: khi máy tính cần cất hàng triệu mục vào 1.000 ngăn, cách đơn giản nhất là lấy mã số của mục chia 1.000 lấy dư để chọn ngăn.
• Số ngẫu nhiên giả: nhiều bộ sinh số ngẫu nhiên kinh điển dùng công thức x mới = (a × x cũ + c) mod m.
• Mật mã: RSA, trao đổi khoá Diffie–Hellman đều là phép luỹ thừa theo một môđun rất lớn.
• Lịch: tính thứ của một ngày bất kỳ, tính năm can chi, đều là bài toán chia lấy dư cho 7, 10, 12, 60.

Góc nhìn hôm nay: tập nghĩ theo phần dư

Thói quen "chỉ giữ phần dư" giúp tính nhẩm nhanh nhiều thứ. Chia 31 viên kẹo cho 4 bạn theo vòng, viên cuối về tay ai? 31 chia 4 dư 3, bạn thứ ba. Một sợi dây đèn nháy lặp 5 màu, bóng thứ 48 màu gì? 48 chia 5 dư 3, cùng màu bóng thứ ba. Ca trực 3 kíp xoay vòng, ngày thứ 100 do kíp nào trực? 100 chia 3 dư 1, kíp của ngày đầu tiên.

Ai muốn học bài bản có thể bắt đầu từ chương đồng dư trong sách giáo khoa chuyên toán bậc trung học cơ sở, rồi đọc thêm phần đầu cuốn Disquisitiones Arithmeticae, bản dịch tiếng Anh vẫn được in lại. Gauss viết rõ ràng đến mức hai thế kỷ sau người đọc vẫn theo kịp.