| Số dư r | Thương q | Hệ số t |
|---|
Đồng hồ đồng dư
Năm giờ sau 9 giờ là 2 giờ, vì 9 + 5 = 14 và 14 hơn 12 hai đơn vị. Đó là số học đồng dư: đếm trên một chiếc đồng hồ bắt đầu lại từ 0 sau n. Chọn một phép toán, nhập n, a và b, và máy tính sẽ đưa ra đáp số với từng bước được viết ra, từ số dư của phép chia đến bình phương liên tiếp và thuật toán Euclid mở rộng, trong khi đồng hồ cho thấy đáp số được tìm ra như thế nào. Chọn một phép toán, rồi nhập môđun n và các số a, b; dùng được số nguyên đến 30 chữ số, kể cả số âm, và n có thể lên đến 10^18. Đồng hồ có n vị trí với 0 ở trên cùng, và kim của nó chỉ vào đáp số. Phép cộng và phép trừ được vẽ thành một đường xoắn ốc gồm b bước, mỗi vòng đủ là một vòng xoắn; phép nhân là các bước nhảy a; lũy thừa là các dây cung a, a², a³ …, khép lại thành một chu trình; nghịch đảo và phép chia là các bội rơi vào 1 hoặc vào a. Các bước trình bày cùng phép tính đó bằng số. Đến mod 20, bảng của phép toán được hiển thị; nhấp vào một ô để dùng các số của nó. Ví dụ điền sẵn một bài toán kinh điển.
Cách nó hoạt động
- Chọn một phép toán: a mod n, phép cộng, phép trừ, phép nhân, phép chia, lũy thừa hoặc nghịch đảo của a.
- Nhập môđun n và các số a, b, hoặc chọn một ví dụ như chữ số tận cùng của 7^2026 hay một thông điệp RSA nhỏ.
- Đọc đáp số và các bước, theo dõi đường đi trên đồng hồ, và đến mod 20, nhấp vào một ô của bảng để thử các số của nó.
a mod n nghĩa là gì
a mod n là số dư khi chia a cho n: 17 mod 5 = 2, vì 17 = 3 × 5 + 2. Số dư luôn từ 0 đến n − 1, kể cả với số âm: −7 mod 3 = 2, vì −7 = −3 × 3 + 2. Trên đồng hồ, điều đó có nghĩa là đi lùi 7 bước từ 0. Hai số có cùng số dư được gọi là đồng dư, viết là 17 ≡ 2 (mod 5), một ký hiệu do Carl Friedrich Gauss đưa ra năm 1801. Tổng, hiệu và tích có thể rút gọn theo mod n ở bất kỳ bước nào, giúp các số luôn nhỏ.
Số học đồng dư được dùng ở đâu
Đồng hồ và lịch hoạt động theo mod 12, mod 24 và mod 7: 100 ngày sau một ngày thứ Tư là thứ Sáu, vì 100 mod 7 = 2. Chữ số kiểm tra dùng nó để phát hiện lỗi gõ, từ mã ISBN-10 (mod 11) đến số thẻ ngân hàng (mod 10) và IBAN (mod 97). Các mật mã dịch chuyển chữ cái theo mod 26, và mã affine cần một nghịch đảo mod 26 để giải mã. RSA, hệ mã bảo vệ phần lớn internet, mã hóa thông điệp m thành m^e mod n và giải mã bằng một lũy thừa khác: với n = 3233, 65^17 mod 3233 = 2790 và 2790^413 mod 3233 = 65.
Câu hỏi thường gặp
Làm thế nào để tính a mod n với một số âm?
Cộng hoặc trừ các bội của n cho đến khi số đó nằm giữa 0 và n − 1. Với −7 mod 3: −7 + 9 = 2, nên đáp số là 2. Một số ngôn ngữ lập trình lại cho −1 với −7 % 3, vì chúng làm tròn thương về phía 0; trong toán học, số dư không bao giờ âm.
Nghịch đảo modulo là gì?
Nghịch đảo của a mod n là số x sao cho a × x ≡ 1 (mod n). Nghịch đảo của 7 mod 26 là 15, vì 7 × 15 = 105 = 4 × 26 + 1. Nó chỉ tồn tại khi a và n không có ước chung, và thuật toán Euclid mở rộng sẽ tìm ra nó. Chia cho a theo mod n nghĩa là nhân với nghịch đảo của nó.
Làm thế nào để tính một lũy thừa như 7^2026 theo mod n?
Bằng bình phương liên tiếp: bình phương 7 hết lần này đến lần khác, mỗi lần rút gọn theo mod n, để có 7^1, 7^2, 7^4, 7^8, v.v., rồi nhân những lũy thừa tạo nên 2026 trong hệ nhị phân. Cách này cần 10 phép bình phương và 7 phép nhân thay vì 2.025 phép nhân, và các số không bao giờ lớn hơn n². 7^2026 có chữ số tận cùng là 9.
Vì sao đồng hồ hiển thị 0 thay vì 12?
Trong số học đồng dư, các số dư chạy từ 0 đến n − 1, nên trên đồng hồ 12 vị trí, giữa trưa là 0. 12 ≡ 0 (mod 12); một chiếc đồng hồ thông thường chỉ in 12 ở chỗ toán học viết 0.
Các số có thể lớn đến mức nào?
a và b có thể có đến 30 chữ số và có thể âm, còn môđun có thể lên đến 10^18. Máy tính làm việc với số nguyên chính xác ngay trong trình duyệt của bạn, nên ngay cả các ví dụ cỡ RSA cũng cho đáp số chính xác, và không có gì được gửi đi đâu cả.
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.
Tới trình chỉnh sửa