Giải thích số học đồng dư
Ai cũng đã từng làm số học đồng dư: 10 giờ sau 8 giờ là 6 giờ, và ngày sau Chủ nhật là thứ Hai. Cách đếm bắt đầu lại từ 0 sau n bước hóa ra có cả một hệ số học hoàn chỉnh của riêng nó, với những quy tắc, những điều bất ngờ và một vị trí trung tâm trong lý thuyết số cũng như trong mật mã học bảo vệ internet.
Số dư và đồng dư
Chia a cho n và chỉ giữ lại số dư: đó là a mod n, một số từ 0 đến n − 1. 26 mod 7 = 5, vì 26 = 3 × 7 + 5. Các số có cùng số dư hành xử như nhau theo mod n, nên ta gọi chúng là đồng dư: 26 ≡ 5 ≡ −2 (mod 7). Carl Friedrich Gauss đưa ra ký hiệu này trong cuốn Disquisitiones Arithmeticae năm 1801, và nó biến những quan sát cũ của Fermat và Euler thành một hệ số học riêng. Trên đồng hồ n vị trí, mọi số nguyên đều rơi vào số dư của nó; các vòng đủ bị bỏ qua.
Cộng, trừ và nhân
Ba phép toán thông thường vẫn hoạt động như bình thường, và bạn có thể rút gọn theo mod n bất cứ lúc nào: số dư của một tổng là số dư của tổng các số dư, và điều tương tự cũng đúng với hiệu và tích. Để tìm chữ số tận cùng của 37 × 48, chỉ cần nhân các chữ số tận cùng: 7 × 8 = 56, nên kết quả tận cùng bằng 6. Đây là điều khiến số học đồng dư rất hữu ích cho máy tính: dù các số lớn đến đâu, giá trị trung gian không bao giờ vượt quá n².
Phép chia cần nghịch đảo
Phép chia là ngoại lệ. 2 × 3 ≡ 2 × 8 (mod 10), vì cả hai đều bằng 6 mod 10, nhưng 3 và 8 khác nhau, nên bạn không thể đơn giản giản ước số 2. Chia cho a nghĩa là nhân với nghịch đảo của nó, tức số x sao cho a × x ≡ 1, và nghịch đảo này tồn tại khi và chỉ khi a và n không có ước chung. Thuật toán Euclid mở rộng tìm ra nó: thuật toán thực hiện các bước chia của Euclid để tìm ước chung lớn nhất và theo dõi một hệ số ở mỗi bước, sao cho khi số dư đạt đến 1 thì hệ số đó chính là nghịch đảo. Khi n là số nguyên tố, mọi số trừ 0 đều có nghịch đảo, và phép chia luôn thực hiện được.
Lũy thừa, Fermat và Euler
Lũy thừa lặp lại. Lấy các lũy thừa của 3 mod 7: 3, 2, 6, 4, 5, 1, rồi lại 3. Độ dài chu trình đó là cấp của 3. Năm 1640, Pierre de Fermat nhận thấy rằng với số nguyên tố p, a^(p − 1) ≡ 1 (mod p) mỗi khi p không chia hết a, nên mọi cấp đều chia hết p − 1. Leonhard Euler đã chứng minh điều này và mở rộng nó cho mọi n, với p − 1 được thay bằng số các giá trị nguyên tố cùng nhau với n. Lũy thừa khổng lồ được tính bằng bình phương liên tiếp: a, a², a⁴, a⁸ … mỗi số là bình phương của số trước, rút gọn theo mod n, rồi nhân lại theo các chữ số nhị phân của số mũ.
Chữ số kiểm tra và lịch
Số học đồng dư phát hiện sai sót. Chữ số cuối cùng của mã ISBN-10 được chọn sao cho tổng có trọng số của cả mười chữ số là bội của 11, nên mọi lỗi sai một chữ số và mọi lỗi đổi chỗ hai chữ số kề nhau đều bị phát hiện. Số thẻ ngân hàng dùng phép kiểm tra Luhn mod 10, còn IBAN dùng phép kiểm tra mod 97. Lịch vận hành theo mod 7: thứ trong tuần của bất kỳ ngày nào cũng có thể tính ra bằng vài số dư, đó là cách hoạt động của lịch vạn niên và quy tắc doomsday.
Mật mã học
Mật mã học hiện đại được xây dựng trên các lũy thừa modulo dễ tính nhưng khó đảo ngược. Trong giao thức trao đổi khóa Diffie–Hellman năm 1976, hai người thống nhất một bí mật chung qua một kênh công khai bằng cách trao đổi các lũy thừa theo mod một số nguyên tố lớn. RSA, được Rivest, Shamir và Adleman công bố năm 1977, mã hóa thông điệp m thành m^e mod n, trong đó n là tích của hai số nguyên tố lớn, và giải mã bằng số mũ thứ hai d mà chỉ người biết hai số nguyên tố đó mới tính được. Trong ví dụ của sách giáo khoa, n = 3233 = 61 × 53, e = 17 và d = 413: 65 trở thành 2790, và 2790 lại trở thành 65.
Tự khám phá
Mở đồng hồ đồng dư để tính a mod n, tổng, hiệu, tích, lũy thừa, nghịch đảo và thương theo mod n, cho các số đến 30 chữ số. Mỗi đáp số đều kèm theo các bước: phép chia có dư, các lũy thừa từ bình phương liên tiếp, hoặc bảng của thuật toán Euclid mở rộng. Đồng hồ vẽ ra cách đi đến đáp số, từ đường xoắn ốc của phép cộng đến chu trình của lũy thừa, và với n nhỏ, bảng của phép toán hiển thị mọi đáp số cùng lúc.
Câu hỏi thường gặp
Ký hiệu ≡ nghĩa là gì?
a ≡ b (mod n) cho biết a và b có cùng số dư khi chia cho n, hay tương đương, n chia hết a − b. 38 ≡ 2 (mod 12), vì 38 − 2 = 36 là bội của 12.
Phép mod có giống toán tử % trong lập trình không?
Với số dương thì có. Với số âm, nhiều ngôn ngữ như C, Java và JavaScript trả về số dư âm: ở đó −7 % 3 bằng −1, trong khi −7 mod 3 = 2. Toán tử % của Python tuân theo quy ước toán học khi n dương.
Cấp của một số theo mod n là gì?
Là số k > 0 nhỏ nhất sao cho a^k ≡ 1 (mod n). Cấp chỉ tồn tại khi a và n không có ước chung. Cấp của 2 mod 7 là 3, vì 2³ = 8 ≡ 1, và cấp của 3 mod 7 là 6, nên các lũy thừa của 3 đi qua mọi số dư khác 0: 3 là căn nguyên thủy mod 7.
Ai đã phát minh ra số học đồng dư?
Số dư đã được dùng từ rất lâu trước đó, chẳng hạn trong định lý số dư Trung Hoa từ thế kỷ 3 đến thế kỷ 5, và bởi Fermat và Euler. Gauss biến nó thành một hệ số học có hệ thống, với ký hiệu đồng dư, vào năm 1801.
Sẵn sàng thử chưa?
Mở PictorX trong trình duyệt — không cần cài đặt, không cần thẻ tín dụng để bắt đầu.
Mở đồng hồ đồng dư