Số học mô-đun — Toán đồng hồ, mod và đồng dư

Số học mô-đun là cách làm việc với các số dư sau khi chia cho một số nguyên dương cố định gọi là mô-đun. Nếu hai số cho cùng một số dư, chúng hoạt động như nhau trong hệ mô-đun đó, nên người ta thường gọi đây là toán đồng hồ.

Trên đồng hồ $12$ giờ, $13$ giờ sẽ rơi vào vị trí $1$ giờ, và $29$ giờ sẽ rơi vào cùng vị trí với $5$ giờ. Chu kỳ lặp lại đó chính là trực giác đằng sau số học mô-đun.

Mod Có Nghĩa Là Gì Trong Số Học Mô-đun

Với một số nguyên $a$ và một số nguyên dương $n$, biểu thức $a \bmod n$ là số dư khi chia $a$ cho $n$.

Ví dụ:

$$29 \bmod 12 = 5$$

vì

$$29 = 12 \cdot 2 + 5$$

Mô-đun là $12$, nên cộng hoặc trừ $12$ sẽ không làm thay đổi vị trí rơi trong chu kỳ.

Đồng Dư Theo Mô-đun $n$ Có Nghĩa Là Gì

Đồng dư là cách viết chính thức để nói rằng hai số nguyên có cùng cách hoạt động theo mô-đun $n$.

$$a \equiv b \pmod n$$

có nghĩa là $a$ và $b$ cho cùng một số dư khi chia cho $n$. Một cách kiểm tra tương đương là

$$n \mid (a-b)$$

nghĩa là “$n$ chia hết $a-b$”.

Vì vậy,

$$29 \equiv 5 \pmod{12}$$

vì $29 - 5 = 24$, và $12$ chia hết $24$.

Sự khác biệt này rất quan trọng:

• $29 \bmod 12 = 5$ là một phát biểu về số dư.
• $29 \equiv 5 \pmod{12}$ là một phát biểu về đồng dư.

Chúng có liên quan với nhau, nhưng không thể thay thế cho nhau.

Ví Dụ Mẫu: $29$ Giờ Sau $8$ Giờ

Giả sử bây giờ là $8$ giờ, và bạn muốn biết $29$ giờ sau sẽ là mấy giờ trên đồng hồ $12$ giờ.

Trước hết, rút gọn $29$ theo mô-đun $12$:

$$29 \bmod 12 = 5$$

Vậy cộng thêm $29$ giờ có cùng tác dụng như cộng thêm $5$ giờ:

$$8 + 29 \equiv 8 + 5 \pmod{12}$$

Khi đó

$$8 + 29 \equiv 13 \equiv 1 \pmod{12}$$

Vậy đồng hồ sẽ chỉ $1$ giờ.

Bước quan trọng là bước rút gọn. Trong mô-đun $12$, thay $29$ bằng $5$ giữ nguyên đáp án và giúp phép tính dễ hơn.

Vì Sao Rút Gọn Trước Giúp Bài Toán Dễ Hơn

Các số lớn thường dễ xử lý hơn sau khi bạn thay chúng bằng một số nhỏ hơn nhưng đồng dư.

Ví dụ, theo mô-đun $7$,

$$100 \equiv 2 \pmod 7$$

vì $100 - 2 = 98$ chia hết cho $7$. Nếu bài toán chỉ quan tâm đến các giá trị theo mô-đun $7$, bạn có thể làm việc với $2$ thay vì $100$.

Những Lỗi Thường Gặp

Nhầm lẫn giữa bằng nhau và đồng dư

$29 \equiv 5 \pmod{12}$ không có nghĩa là $29 = 5$. Nó có nghĩa là chúng thuộc cùng một lớp số dư theo mô-đun $12$.

Quên rằng mô-đun rất quan trọng

$17 \equiv 5 \pmod{12}$ là đúng, nhưng $17 \equiv 5 \pmod{10}$ là sai. Đồng dư luôn gắn với một mô-đun cụ thể.

Xem mod như phép chia thông thường

$29 \bmod 12$ là số dư $5$, không phải thương $2$ và cũng không phải phân số $29/12$.

Cho rằng toán tử % trong phần mềm luôn theo cùng một quy ước toán học

Với các số dương, toán tử % trong ngôn ngữ lập trình thường khớp với ý tưởng số dư mà học sinh học đầu tiên. Với số âm, quy ước có thể khác nhau, nên kết quả có thể không trùng với số dư không âm nhỏ nhất được dùng trong nhiều khóa học toán.

Số Học Mô-đun Được Dùng Ở Đâu

Bạn sẽ gặp số học mô-đun bất cứ khi nào các giá trị lặp lại theo chu kỳ: đồng hồ, các ngày trong tuần, hệ thống chữ số kiểm tra, hàm băm và nhiều phần của lý thuyết số.

Nó cũng xuất hiện trong mật mã học, nhưng ý tưởng cơ bản vẫn vậy: các số được nhóm theo số dư của chúng, và các số đồng dư có thể được xem là tương đương trong hệ đó.

Thử Một Bài Tương Tự

$100$ ngày sau thứ Hai sẽ là thứ mấy? Vì các ngày lặp lại theo mô-đun $7$, hãy bắt đầu bằng cách rút gọn $100$ theo mô-đun $7$ trước khi trả lời.

Nếu muốn có thêm một trường hợp để so sánh, hãy thử phiên bản của riêng bạn trong GPAI Solver và xem liệu rút gọn trước có làm bài ngắn hơn không.