Máy tính modulo

Hai quy ước cho số âm

Với toán hạng dương, mọi quy ước đều thống nhất: 17 mod 5 = 2. Với số âm, các ngôn ngữ khác nhau:

Phép chia làm tròn xuống: thương được làm tròn về phía −∞. Phần dư luôn mang dấu của số chia: cùng dấu với b. Phép chia cắt bỏ: thương được làm tròn về phía 0. Phần dư mang dấu của số bị chia: cùng dấu với a.

Với a = -17, b = 5:

• Cắt bỏ: q = -3 (làm tròn về 0), r = -17 − (-3)·5 = -2.
• Làm tròn xuống: q = -4 (làm tròn về -∞), r = -17 − (-4)·5 = 3.

Cả hai đều đúng theo quy ước của mình. Hãy chọn cái phù hợp với ngôn ngữ của bạn.

Modulo xuất hiện ở đâu

• Thời gian. Số phút trong một giờ, các ngày trong tuần, số giây trong một ngày, tất cả đều là số học modulo.
• Bảng băm. hash(key) mod table_size chọn một bucket.
• Lập lịch xoay vòng (round-robin). task_i mod worker_count phân bổ công việc.
• Mật mã học. RSA và Diffie-Hellman được xây trên mod n với các số nguyên tố cực lớn.
• Mỗi hàng thứ N. Trong SQL: WHERE id % 3 = 0.
• Kiểm tra chẵn/lẻ. n mod 2 == 0 nghĩa là số chẵn.
• Mẫu xen kẽ. Kẻ sọc theo hàng, tô màu cách một phần tử.
• Bộ đệm vòng. (index + 1) mod size quay lại đầu.

Các đẳng thức hữu ích

• (a + b) mod n = ((a mod n) + (b mod n)) mod n
• (a · b) mod n = ((a mod n) · (b mod n)) mod n
• (a^k) mod n có thể tính bằng lũy thừa modular nhanh trong O(log k), thiết yếu cho mật mã số lớn.
• a mod 1 = 0 với mọi số nguyên a.
• a mod a = 0.

Modulo số thập phân

Với số thực, định nghĩa tự nhiên là a mod b = a − b · floor(a/b). 7.5 mod 2.5 = 0 vì 7,5 là bội số chính xác. 7.6 mod 2.5 = 0.1.

Toán tử % của JavaScript hoạt động trên số thực; fmod của Python thực hiện modulo thực kiểu cắt bỏ; % của Python thực hiện modulo thực kiểu làm tròn xuống.

Ví dụ có lời giải

• 100 mod 7: 100 = 14·7 + 2, nên phần dư là 2.
• 25 mod 4: 25 = 6·4 + 1, nên phần dư là 1.
• -10 mod 3 (làm tròn xuống): -10 = -4·3 + 2, phần dư 2. (Cắt bỏ sẽ cho -1.)
• 17.5 mod 5: 17,5 = 3·5 + 2,5, phần dư 2,5.