Định nghĩa

Phép lấy phần dư

Xét $a, b \in \mathbb{Z}, b \neq 0$ , kí hiệu $a \bmod b$ là số dư khi chia $a$ cho $b$ . Ví dụ: $30 \bmod 7 = 2\\ 10 \bmod 2 = 0\\ -12 \bmod 5 = 3$ Ta thấy, $-12 \bmod 5$ có thể có 2 kết quả là $-2$ hoặc $3$ . Thông thường, khi làm toán thì số dương được ưu tiên, tuy nhiên khi lập trình phép mod này sẽ cho kết quả âm.

Định nghĩa một cách chuẩn mực, xét phép chia Euclide $a$ cho $b$ : $q \in \mathbb{Z}\\ a = bq + r\\ |r| < |b|$ Thì ta có $a \bmod b = r$ .

Đồng dư

Xét số nguyên $n > 1$ và 2 số nguyên $a, b$ , ta kí hiệu $a \equiv b \pmod n$ khi $a$ và $b$ có cùng số dư khi chia cho $n$ , đọc là $a$ đồng dư với $b$ modulo $n$ .

Ví dụ: $12 \equiv 7 \equiv 2 \pmod 5 \\ -3 \equiv 2 \pmod 5$

Như vậy, $a \equiv b \pmod n \iff a \bmod n = b \bmod n$ .

Kí hiệu $\bar{a}_n$ là tập hợp tất cả các số đồng dư với $a$ trong modulo $n$ :

$\bar{a}_n = \{x \mid x \equiv a \pmod n \}$

Ta có vành $\mathbb{Z}/n$ là tập hợp tất cả các $\bar{a}_n$ :

$\mathbb{Z}/n = \{\bar{a}_n \mid a \in \mathbb{Z}\}$

Ví dụ: $\bar{8}_5 = \bar{3}_5 = \{\dots,-7, -2, 3, 8, 13,\dots\}\\ \mathbb{Z}/5 = \{\bar{0}_5, \bar{1}_5, \bar{2}_5, \bar{3}_5, \bar{4}_5\}$

Xem thêm về vành - Ring.

Phép toán trên vành modulo và một số tính chất

Phần này xét phép cộng và phép nhân. Phép cộng và phép nhân được định nghĩa thông qua lý thuyết vành:

$\bar{a}_n + \bar{b}_n = \overline{a + b}_n\\ \bar{a}_n - \bar{b}_n = \overline{a - b}_n\\ \bar{a}_n \bar{b}_n = \overline{a b}_n$

Ví dụ:

$\bar{6}_{10} + \bar{8}_{10} = \overline{6 + 8}_{10} = \overline{14}_{10} = \bar{4}_{10}$ . Ý nghĩa là: “số chia 10 dư 6” cộng cho “số chia 10 dư 8” sẽ cho kết quả là “số chia 10 dư 4”.

Ta cũng có thể sử dụng kí hiệu đồng dư: $6 + 8 \equiv 14 \equiv 4 \pmod{10}$

Dấu $\equiv$ cũng có tính chất tương tự như dấu $=$ :

$a \equiv a \pmod n$
$a \equiv b \pmod n \iff b \equiv a \pmod n$
Nếu $a \equiv b \pmod n$ và $b \equiv c \pmod n$ thì $a \equiv c \pmod n$

Xét $a, b, k \in \mathbb{Z}$ , nếu $a \equiv b \pmod n$ thì ta có các tính chất sau:

$-a \equiv -b \pmod n$
$a + k \equiv b + k \pmod n$
$ka \equiv kb \pmod n$
$a^k \equiv b^k \pmod n$
Tổng quát, ta có $p(a) \equiv p(b) \pmod n$ , với $p$ là đa thức có hệ số nguyên.

Ngược lại, ta có:

$a + k \equiv b + k \pmod n \iff a \equiv b \pmod n$
Nếu $ka \equiv kb \pmod n$ và $k$ nguyên tố cùng nhau với $n$ thì $a \equiv b \pmod n$

Xét $a_1 \equiv b_1 \pmod n$ và $a_2 \equiv b_2 \pmod n$ , ta có:

$a_1 + a_2 \equiv b_1 + b_2 \pmod n$
$a_1 - a_2 \equiv b_1 - b_2 \pmod n$
$a_1 a_2 \equiv b_1 b_2 \pmod n$

Ví dụ ứng dụng toán đồng dư

Trong ví dụ sau mình sẽ chứng minh “Một số chia hết cho 3 khi và chỉ khi tổng các chữ số của số đó chia hết cho 3”.

Xét số $A$ có $n$ chữ số trong hệ thập phân: $a_0, a_1, a_2,\dots,a_{n-1}$ , ta có:

$A = a_0 + 10 a_1 + 10^2 a_2 + \dots + 10^{n-1} a_{n-1}$

Theo bài toán thì ta có $A$ chia hết cho 3, có nghĩa là: $A \equiv 0 \pmod 3$

Tương đương với:

$a_0 + 10 a_1 + 10^2 a_2 + \dots + 10^{n-1} a_{n-1} \equiv 0 \pmod 3$

Mặt khác, vì $10 \equiv 1 \pmod 3$ nên ta có thể thay 10 bằng 1 trong biểu thức ở trên, ta có:

$a_0 + 1 a_1 + 1^2 a_2 + \dots + 1^{n-1} a_{n-1} \equiv 0 \pmod 3\\ \iff a_0 + a_1 + a_2 + \dots + a_{n-1} \equiv 0 \pmod 3$

Chứng minh xong. Áp dụng kĩ thuật tương tự ta cũng có thể chứng minh các số chia hết cho 9 sẽ có tổng các chữ số chia hết cho 9.