Bài học

Đồng dư thức và số dư — nền tảng suy luận

Mục tiêu bài học

Sau bài này, em giải thích được thế nào là đồng dư thức ( $a \equiv b \pmod{n}$ ), dùng đúng hai tính chất cộng và nhân của đồng dư, và áp dụng chúng để tìm số dư của những lũy thừa rất lớn (như $7^{100}$ chia cho 5) mà không cần nhân trực tiếp. Đây là công cụ nền cho toàn bộ Chương 1, Chương 4 và nhiều bài toán ở các chương sau của khóa học.

Sau bài này, em giải thích được thế nào là **đồng dư thức** ($a \equiv b \pmod{n}$), dùng đúng hai tính chất cộng và nhân của đồng dư, và áp dụng chúng để tìm số dư của những lũy thừa rất lớn (như $7^{100}$ chia cho 5) mà không cần nhân trực tiếp. Đây là công cụ nền cho toàn bộ Chương 1, Chương 4 và nhiều bài toán ở các chương sau của khóa học.

Kiến thức cần có

Em đã biết phép chia có dư từ Lớp 6: mọi số nguyên $a$ chia cho số nguyên dương $n$ đều viết được dưới dạng $a = nq + r$ với $0 \le r < n$ . Đồng dư thức ( $a \equiv b \pmod{n}$ , đọc là "a đồng dư với b theo modulo n") là cách viết gọn cho việc " $a$ và $b$ có cùng số dư khi chia cho $n$ " — khái niệm này không nằm trong chương trình chuẩn Lớp 9, ta đưa vào như một Mở rộng dành cho HSG vì nó là ngôn ngữ bắt buộc để trình bày gọn các chứng minh chia hết và vô nghiệm ở các bài sau.

Em đã biết phép chia có dư từ Lớp 6: mọi số nguyên $a$ chia cho số nguyên dương $n$ đều viết được dưới dạng $a = nq + r$ với $0 \le r < n$. **Đồng dư thức** ($a \equiv b \pmod{n}$, đọc là "a đồng dư với b theo modulo n") là cách viết gọn cho việc "$a$ và $b$ có cùng số dư khi chia cho $n$" — khái niệm này **không nằm trong chương trình chuẩn Lớp 9**, ta đưa vào như một **Mở rộng dành cho HSG** vì nó là ngôn ngữ bắt buộc để trình bày gọn các chứng minh chia hết và vô nghiệm ở các bài sau.

So với đề chuẩn lớp 9: một câu hỏi thông thường chỉ hỏi " $123$ chia $7$ dư bao nhiêu?" — em chia trực tiếp và ra ngay $123 = 7 \times 17 + 4$ , dư $4$ . Nhưng nếu đề hỏi " $7^{100}$ chia cho $5$ dư bao nhiêu?" thì phép chia trực tiếp là bất khả thi (số đó có hơn 80 chữ số). Đây chính là ranh giới giữa bài chuẩn và bài HSG: bài HSG đòi hỏi công cụ suy luận về số dư, không phải phép tính trực tiếp.

**So với đề chuẩn lớp 9:** một câu hỏi thông thường chỉ hỏi "$123$ chia $7$ dư bao nhiêu?" — em chia trực tiếp và ra ngay $123 = 7 \times 17 + 4$, dư $4$. Nhưng nếu đề hỏi "$7^{100}$ chia cho $5$ dư bao nhiêu?" thì phép chia trực tiếp là bất khả thi (số đó có hơn 80 chữ số). Đây chính là ranh giới giữa bài chuẩn và bài HSG: **bài HSG đòi hỏi công cụ suy luận về số dư, không phải phép tính trực tiếp**.

Bài toán khởi động

Không tính trực tiếp $7^{100}$ , hãy tìm số dư khi chia $7^{100}$ cho $5$ . Nếu chỉ có phép chia thông thường, bài toán này là không thể làm nổi trong thời gian thi. Ta cần một công cụ khác.

Không tính trực tiếp $7^{100}$, hãy tìm số dư khi chia $7^{100}$ cho $5$. Nếu chỉ có phép chia thông thường, bài toán này là không thể làm nổi trong thời gian thi. Ta cần một công cụ khác.

Ý tưởng cốt lõi

Định nghĩa: $a \equiv b \pmod{n}$ nghĩa là $a - b$ chia hết cho $n$ (tương đương: $a$ và $b$ có cùng số dư khi chia cho $n$ ). Hai tính chất quan trọng nhất, và là chìa khóa của cả bài học: nếu $a \equiv b \pmod n$ và $c \equiv d \pmod n$ thì (1) cộng được: $a + c \equiv b + d \pmod n$ , và (2) nhân được: $a \cdot c \equiv b \cdot d \pmod n$ . Từ tính nhân được suy ra hệ quả cực kỳ hữu ích: nếu $a \equiv r \pmod n$ thì $a^k \equiv r^k \pmod n$ với mọi số mũ tự nhiên $k$ — nghĩa là ta có thể thay số lớn bằng số dư nhỏ của nó rồi mới nâng lũy thừa, thay vì nâng lũy thừa số lớn rồi mới chia.

**Định nghĩa:** $a \equiv b \pmod{n}$ nghĩa là $a - b$ chia hết cho $n$ (tương đương: $a$ và $b$ có cùng số dư khi chia cho $n$). Hai tính chất quan trọng nhất, và là chìa khóa của cả bài học: nếu $a \equiv b \pmod n$ và $c \equiv d \pmod n$ thì **(1) cộng được:** $a + c \equiv b + d \pmod n$, và **(2) nhân được:** $a \cdot c \equiv b \cdot d \pmod n$. Từ tính nhân được suy ra hệ quả cực kỳ hữu ích: nếu $a \equiv r \pmod n$ thì $a^k \equiv r^k \pmod n$ với mọi số mũ tự nhiên $k$ — nghĩa là **ta có thể thay số lớn bằng số dư nhỏ của nó rồi mới nâng lũy thừa**, thay vì nâng lũy thừa số lớn rồi mới chia.

Vì sao nghĩ ra được ý này? Một học sinh giỏi khi thấy số mũ rất lớn ( $100$ , $2024$ , ...) sẽ tự hỏi: "số dư của các lũy thừa liên tiếp có lặp lại theo chu kỳ không?" Vì chỉ có $n$ số dư có thể xảy ra khi chia cho $n$ (là $0, 1, \ldots, n-1$ ), dãy số dư của $a^1, a^2, a^3, \ldots$ khi chia cho $n$ chắc chắn phải lặp lại sau tối đa $n$ bước — đây là một dạng "nguyên lý chuồng bồ câu" ẩn bên dưới. Việc còn lại chỉ là tìm ra chu kỳ đó bằng cách tính vài số mũ đầu tiên.

**Vì sao nghĩ ra được ý này?** Một học sinh giỏi khi thấy số mũ rất lớn ($100$, $2024$, ...) sẽ tự hỏi: "số dư của các lũy thừa liên tiếp có lặp lại theo chu kỳ không?" Vì chỉ có $n$ số dư có thể xảy ra khi chia cho $n$ (là $0, 1, \ldots, n-1$), dãy số dư của $a^1, a^2, a^3, \ldots$ khi chia cho $n$ chắc chắn phải lặp lại sau tối đa $n$ bước — đây là một dạng "nguyên lý chuồng bồ câu" ẩn bên dưới. Việc còn lại chỉ là tìm ra chu kỳ đó bằng cách tính vài số mũ đầu tiên.

Ví dụ áp dụng

Ví dụ

Ví dụ 1 — Tìm chu kỳ số dư của lũy thừa

1
Tìm số dư khi chia $2^{100}$ cho $7$ .
Tìm số dư khi chia $2^{100}$ cho $7$.
2
Tính các số dư liên tiếp của $2^k$ khi chia cho $7$ : $2^1 \equiv 2$ , $2^2 \equiv 4$ , $2^3 \equiv 8 \equiv 1 \pmod 7$ . Vì $2^3 \equiv 1 \pmod 7$ , nhân hai vế với $2^3$ ta lại được $2^6 \equiv 1$ , rồi $2^9 \equiv 1, \ldots$ — chu kỳ của số dư là $3$ .
Tính các số dư liên tiếp của $2^k$ khi chia cho $7$: $2^1 \equiv 2$, $2^2 \equiv 4$, $2^3 \equiv 8 \equiv 1 \pmod 7$. Vì $2^3 \equiv 1 \pmod 7$, nhân hai vế với $2^3$ ta lại được $2^6 \equiv 1$, rồi $2^9 \equiv 1, \ldots$ — chu kỳ của số dư là $3$.
3
Viết $100 = 3 \times 33 + 1$ . Khi đó $2^{100} = (2^3)^{33} \cdot 2^1 \equiv 1^{33} \cdot 2 \equiv 2 \pmod 7$ (dùng đúng tính nhân được của đồng dư ở trên: thay $2^3$ bằng số dư $1$ của nó).
Viết $100 = 3 \times 33 + 1$. Khi đó $2^{100} = (2^3)^{33} \cdot 2^1 \equiv 1^{33} \cdot 2 \equiv 2 \pmod 7$ (dùng đúng tính nhân được của đồng dư ở trên: thay $2^3$ bằng số dư $1$ của nó).
4
Vậy $2^{100}$ chia cho $7$ dư $2$ . Toàn bộ quá trình không cần tính $2^{100}$ (một số có 31 chữ số) — chỉ cần ba phép tính nhỏ và một phép chia số mũ cho chu kỳ.
Vậy $2^{100}$ chia cho $7$ dư $2$. Toàn bộ quá trình không cần tính $2^{100}$ (một số có 31 chữ số) — chỉ cần ba phép tính nhỏ và một phép chia số mũ cho chu kỳ.
5
Ta có $2^1\equiv2$ , $2^2\equiv4$ , $2^3\equiv8\equiv1\pmod7$ (1). Vì $2^3\equiv1\pmod7$ , theo tính nhân được của đồng dư, với mọi $k$ : $2^{3k}\equiv1^k=1\pmod7$ . Ta có $100=3\times33+1$ . Suy ra $2^{100}=(2^3)^{33}\cdot2^1\equiv1^{33}\cdot2\equiv2\pmod7$ theo (1) và tính nhân được của đồng dư. Vậy $2^{100}$ chia cho $7$ dư $2$ .
Ta có $2^1\equiv2$, $2^2\equiv4$, $2^3\equiv8\equiv1\pmod7$ (1). Vì $2^3\equiv1\pmod7$, theo tính nhân được của đồng dư, với mọi $k$: $2^{3k}\equiv1^k=1\pmod7$. Ta có $100=3\times33+1$. Suy ra $2^{100}=(2^3)^{33}\cdot2^1\equiv1^{33}\cdot2\equiv2\pmod7$ theo (1) và tính nhân được của đồng dư. Vậy $2^{100}$ chia cho $7$ dư $2$.
6
Nếu đổi cơ số $2$ thành $5$ , giữ modulo $7$ : xét $5^{100}\pmod7$ . Ta có $5^1\equiv5,5^2\equiv4,5^3\equiv6,5^4\equiv2,5^5\equiv3,5^6\equiv1\pmod7$ — chu kỳ dài $6$ (dài hơn hẳn chu kỳ $3$ của cơ số $2$ ). Vì $100=6\times16+4$ , $5^{100}\equiv5^4\equiv2\pmod7$ — cùng quy trình, chỉ khác độ dài chu kỳ.
Nếu đổi cơ số $2$ thành $5$, giữ modulo $7$: xét $5^{100}\pmod7$. Ta có $5^1\equiv5,5^2\equiv4,5^3\equiv6,5^4\equiv2,5^5\equiv3,5^6\equiv1\pmod7$ — chu kỳ dài $6$ (dài hơn hẳn chu kỳ $3$ của cơ số $2$). Vì $100=6\times16+4$, $5^{100}\equiv5^4\equiv2\pmod7$ — cùng quy trình, chỉ khác độ dài chu kỳ.

Số dư của

2^k

chia cho

7

chỉ lặp lại trong tập

\{1, 2, 4\}

theo đúng thứ tự — đây là toàn bộ "vũ trụ" số dư có thể xảy ra, không bao giờ ra số nào khác.Số dư của $2^k$ chia cho $7$ chỉ lặp lại trong tập $\{1, 2, 4\}$ theo đúng thứ tự — đây là toàn bộ "vũ trụ" số dư có thể xảy ra, không bao giờ ra số nào khác.

Ví dụ

Ví dụ 2 — Giải bài toán khởi động:

7^{100}

chia cho 5Ví dụ 2 — Giải bài toán khởi động: $7^{100}$ chia cho 5

1
Vì $7 \equiv 2 \pmod 5$ , theo tính nhân được, $7^{100} \equiv 2^{100} \pmod 5$ — ta chỉ cần làm việc với $2^{100}$ thay vì $7^{100}$ .
Vì $7 \equiv 2 \pmod 5$, theo tính nhân được, $7^{100} \equiv 2^{100} \pmod 5$ — ta chỉ cần làm việc với $2^{100}$ thay vì $7^{100}$.
2
$2^1 \equiv 2$ , $2^2 \equiv 4$ , $2^3 \equiv 8 \equiv 3$ , $2^4 \equiv 16 \equiv 1 \pmod 5$ . Chu kỳ là $4$ (vì $2^4 \equiv 1$ ).
$2^1 \equiv 2$, $2^2 \equiv 4$, $2^3 \equiv 8 \equiv 3$, $2^4 \equiv 16 \equiv 1 \pmod 5$. Chu kỳ là $4$ (vì $2^4 \equiv 1$).
3
Viết $100 = 4 \times 25 + 0$ , tức $100$ chia hết cho $4$ . Khi đó $2^{100} = (2^4)^{25} \equiv 1^{25} \equiv 1 \pmod 5$ .
Viết $100 = 4 \times 25 + 0$, tức $100$ chia hết cho $4$. Khi đó $2^{100} = (2^4)^{25} \equiv 1^{25} \equiv 1 \pmod 5$.
4
$7^{100}$ chia cho $5$ dư $1$ . Lưu ý điểm tinh tế: khi số mũ chia hết đúng cho chu kỳ (dư $0$ ), ta dùng lũy thừa bằng đúng chu kỳ ( $2^4$ ) chứ không phải $2^0$ , vì $100 = 4 \times 25$ nghĩa là lấy trọn $25$ lần chu kỳ.
$7^{100}$ chia cho $5$ dư $1$. Lưu ý điểm tinh tế: khi số mũ chia hết đúng cho chu kỳ (dư $0$), ta dùng lũy thừa bằng đúng chu kỳ ($2^4$) chứ không phải $2^0$, vì $100 = 4 \times 25$ nghĩa là lấy trọn $25$ lần chu kỳ.
5
Ta có $7\equiv2\pmod5$ . Theo tính nhân được của đồng dư, $7^{100}\equiv2^{100}\pmod5$ (1). Xét chu kỳ của $2^k\pmod5$ : $2^1\equiv2,2^2\equiv4,2^3\equiv3,2^4\equiv1\pmod5$ — chu kỳ dài $4$ (2). Ta có $100=4\times25+0$ . Kết hợp (1) và (2): $2^{100}=(2^4)^{25}\equiv1^{25}\equiv1\pmod5$ , do đó $7^{100}\equiv1\pmod5$ . Vậy $7^{100}$ chia cho $5$ dư $1$ .
Ta có $7\equiv2\pmod5$. Theo tính nhân được của đồng dư, $7^{100}\equiv2^{100}\pmod5$ (1). Xét chu kỳ của $2^k\pmod5$: $2^1\equiv2,2^2\equiv4,2^3\equiv3,2^4\equiv1\pmod5$ — chu kỳ dài $4$ (2). Ta có $100=4\times25+0$. Kết hợp (1) và (2): $2^{100}=(2^4)^{25}\equiv1^{25}\equiv1\pmod5$, do đó $7^{100}\equiv1\pmod5$. Vậy $7^{100}$ chia cho $5$ dư $1$.
6
Nếu đổi số mũ từ $100$ thành $102$ (giữ nguyên cơ số và modulo): $2^{102}=2^{100}\cdot2^2\equiv1\cdot4=4\pmod5$ , nên $7^{102}$ chia cho $5$ dư $4$ — số dư đổi khác dù cùng cơ số và modulo, vì số mũ không còn là bội đúng của chu kỳ.
Nếu đổi số mũ từ $100$ thành $102$ (giữ nguyên cơ số và modulo): $2^{102}=2^{100}\cdot2^2\equiv1\cdot4=4\pmod5$, nên $7^{102}$ chia cho $5$ dư $4$ — số dư đổi khác dù cùng cơ số và modulo, vì số mũ không còn là bội đúng của chu kỳ.

Ví dụ

Ví dụ 3 — Chứng minh một số chính phương chia cho 4 chỉ dư 0 hoặc 1

1
Chứng minh rằng với mọi số nguyên $n$ , số $n^2$ chia cho $4$ chỉ có thể dư $0$ hoặc $1$ , không bao giờ dư $2$ hoặc $3$ .
Chứng minh rằng với mọi số nguyên $n$, số $n^2$ chia cho $4$ chỉ có thể dư $0$ hoặc $1$, không bao giờ dư $2$ hoặc $3$.
2
Mọi số nguyên $n$ đều thuộc một trong hai dạng: $n = 2k$ (chẵn) hoặc $n = 2k+1$ (lẻ), với $k$ nguyên.
Mọi số nguyên $n$ đều thuộc một trong hai dạng: $n = 2k$ (chẵn) hoặc $n = 2k+1$ (lẻ), với $k$ nguyên.
3
$n^2 = (2k)^2 = 4k^2$ , chia hết cho $4$ , tức $n^2 \equiv 0 \pmod 4$ .
$n^2 = (2k)^2 = 4k^2$, chia hết cho $4$, tức $n^2 \equiv 0 \pmod 4$.
4
$n^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 4(k^2+k) + 1$ , chia cho $4$ dư $1$ , tức $n^2 \equiv 1 \pmod 4$ .
$n^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 4(k^2+k) + 1$, chia cho $4$ dư $1$, tức $n^2 \equiv 1 \pmod 4$.
5
Vì mọi $n$ chỉ rơi vào một trong hai trường hợp trên, số dư của $n^2$ khi chia cho $4$ chỉ có thể là $0$ hoặc $1$ . Kết quả này — gọi là bảng thặng dư bình phương mod 4 — sẽ là công cụ chính của Bài 2 ngay sau đây, và còn được dùng lại nhiều lần ở Chương 4.
Vì mọi $n$ chỉ rơi vào một trong hai trường hợp trên, số dư của $n^2$ khi chia cho $4$ chỉ có thể là $0$ hoặc $1$. Kết quả này — gọi là **bảng thặng dư bình phương mod 4** — sẽ là công cụ chính của Bài 2 ngay sau đây, và còn được dùng lại nhiều lần ở Chương 4.
6
Xét $n$ theo tính chẵn lẻ: mọi số nguyên $n$ có dạng $n=2k$ hoặc $n=2k+1$ ( $k\in\mathbb{Z}$ ) — xét đủ hai trường hợp. Trường hợp $n=2k$ : $n^2=4k^2$ chia hết cho $4$ , tức $n^2\equiv0\pmod4$ (1). Trường hợp $n=2k+1$ : $n^2=4k^2+4k+1=4(k^2+k)+1$ , do đó $n^2\equiv1\pmod4$ (2). Kết hợp (1) và (2), với mọi $n$ nguyên: $n^2\pmod4\in\{0,1\}$ . Vậy số chính phương chia cho $4$ chỉ có thể dư $0$ hoặc $1$ , không bao giờ dư $2$ hoặc $3$ .
Xét $n$ theo tính chẵn lẻ: mọi số nguyên $n$ có dạng $n=2k$ hoặc $n=2k+1$ ($k\in\mathbb{Z}$) — xét đủ hai trường hợp. Trường hợp $n=2k$: $n^2=4k^2$ chia hết cho $4$, tức $n^2\equiv0\pmod4$ (1). Trường hợp $n=2k+1$: $n^2=4k^2+4k+1=4(k^2+k)+1$, do đó $n^2\equiv1\pmod4$ (2). Kết hợp (1) và (2), với mọi $n$ nguyên: $n^2\pmod4\in\{0,1\}$. Vậy số chính phương chia cho $4$ chỉ có thể dư $0$ hoặc $1$, không bao giờ dư $2$ hoặc $3$.
7
Thay modulo $4$ bằng modulo $3$ : xét đủ ba lớp dư $n\equiv0,1,2\pmod3$ , ta chứng minh tương tự $n^2\pmod3\in\{0,1\}$ — bảng dư hẹp hơn ba giá trị khả dĩ, đúng như sẽ dùng ngay ở Bài học tiếp theo.
Thay modulo $4$ bằng modulo $3$: xét đủ ba lớp dư $n\equiv0,1,2\pmod3$, ta chứng minh tương tự $n^2\pmod3\in\{0,1\}$ — bảng dư hẹp hơn ba giá trị khả dĩ, đúng như sẽ dùng ngay ở Bài học tiếp theo.

Bẫy thường gặp

(1) Nhầm $a \equiv b \pmod n$ với $a = b$ — đồng dư chỉ nói về số dư, không nói hai số bằng nhau. (2) Đồng dư cộng và nhân được, nhưng không được tự ý "chia" hai vế của một đồng dư trừ khi số chia nguyên tố cùng nhau với $n$ (đây là lý do vì sao Ví dụ 2 phải rút gọn cơ số bằng cách thay $7$ bởi số dư $2$ của nó, chứ không "chia" hai vế cho gì cả). (3) Khi tìm chu kỳ, phải tính từ $k=1$ và kiểm tra chu kỳ đó thực sự lặp lại (bằng cách nhân tiếp một bước), không được vội kết luận sau một lần trùng ngẫu nhiên.

(1) Nhầm $a \equiv b \pmod n$ với $a = b$ — đồng dư chỉ nói về số dư, không nói hai số bằng nhau. (2) Đồng dư cộng và nhân được, nhưng **không được tự ý "chia" hai vế của một đồng dư** trừ khi số chia nguyên tố cùng nhau với $n$ (đây là lý do vì sao Ví dụ 2 phải rút gọn cơ số bằng cách thay $7$ bởi số dư $2$ của nó, chứ không "chia" hai vế cho gì cả). (3) Khi tìm chu kỳ, phải tính từ $k=1$ và kiểm tra chu kỳ đó **thực sự lặp lại** (bằng cách nhân tiếp một bước), không được vội kết luận sau một lần trùng ngẫu nhiên.

Luyện tập có hướng dẫn

Luyện tập độc lập

Thử thách

Điều cần nhớ

Đồng dư thức cho phép thay số lớn bằng số dư nhỏ của nó trước khi cộng, nhân, hoặc nâng lũy thừa — nhưng đồng dư không cho phép "chia" tùy tiện. Chu kỳ số dư của một lũy thừa luôn tồn tại (vì chỉ có hữu hạn số dư khả dĩ) và là chìa khóa để xử lý số mũ rất lớn: rút gọn cơ số về số dư nhỏ, tìm chu kỳ, rồi chia số mũ cho chu kỳ.

Đồng dư thức cho phép **thay số lớn bằng số dư nhỏ của nó** trước khi cộng, nhân, hoặc nâng lũy thừa — nhưng đồng dư **không** cho phép "chia" tùy tiện. Chu kỳ số dư của một lũy thừa luôn tồn tại (vì chỉ có hữu hạn số dư khả dĩ) và là chìa khóa để xử lý số mũ rất lớn: rút gọn cơ số về số dư nhỏ, tìm chu kỳ, rồi chia số mũ cho chu kỳ.

Bài tiếp theo: ta đã thấy số chính phương chia cho $4$ chỉ dư $0$ hoặc $1$ (Ví dụ 3). Bài học tiếp theo sẽ mở rộng bảng thặng dư này sang mod $3$ và mod $8$ , rồi dùng chính những bảng dư đó để chứng minh một phương trình vô nghiệm — kỹ thuật cốt lõi cho toàn bộ Chương 4 của khóa học.

**Bài tiếp theo:** ta đã thấy số chính phương chia cho $4$ chỉ dư $0$ hoặc $1$ (Ví dụ 3). Bài học tiếp theo sẽ mở rộng bảng thặng dư này sang mod $3$ và mod $8$, rồi dùng chính những bảng dư đó để **chứng minh một phương trình vô nghiệm** — kỹ thuật cốt lõi cho toàn bộ Chương 4 của khóa học.