Định lý phần dư Trung Hoa: giải bài toán đồng dư

Định lý phần dư Trung Hoa: ứng dụng xử lý bài toán đồng dư và chia hết

Phần 1. Bài toán cổ mà cách giải vẫn là thử

Đề quen thuộc trong đề thi học sinh giỏi và cả đề khảo sát: "Một số tự nhiên chia 3 dư 2, chia 5 dư 3, chia 7 dư 2. Tìm số nhỏ nhất thoả mãn." Cách làm phổ biến ở lớp là liệt kê: viết dãy số chia 3 dư 2 (2, 5, 8, 11, …), dò xem số nào chia 5 dư 3, rồi lại dò tiếp điều kiện thứ ba. Với ba điều kiện, học sinh có thể phải thử vài chục số.

Cách ấy không sai, nhưng nó không mở rộng được. Đổi số chia thành $11$ , $13$ , $17$ thì liệt kê trở nên vô vọng — và đề thi biết điều đó.

Định lý phần dư Trung Hoa (Chinese Remainder Theorem) trả lời trọn vẹn câu hỏi: khi nào hệ điều kiện như vậy có nghiệm, có bao nhiêu nghiệm, và tìm chúng bằng cách nào. Tên gọi đến từ bài toán "Hàn Tín điểm binh" trong Tôn Tử toán kinh thế kỷ thứ 3, nhưng nó vẫn là công cụ chuẩn trong số học hiện đại.

Phần 2. Bản chất: hai chu kỳ gặp nhau ở một chu kỳ dài hơn

Lưới số từ 0 đến 14 với số dư theo mod 3 và mod 5

Điều kiện "chia 3 dư 2" mô tả một dãy tuần hoàn chu kỳ 3. Điều kiện "chia 5 dư 3" mô tả một dãy tuần hoàn chu kỳ 5. Câu hỏi là: hai dãy ấy trùng nhau ở đâu?

Nếu $3$ và $5$ nguyên tố cùng nhau, mẫu hình kết hợp lặp lại đúng mỗi $3 \times 5 = 15$ bước, và trong mỗi chu kỳ $15$ có đúng một giá trị thoả cả hai. Nhìn hình: chỉ $x = 8$ .

Phát biểu tổng quát: nếu $m_1, m_2, \dots, m_k$ đôi một nguyên tố cùng nhau thì hệ

x \equiv a_1 \pmod{m_1}, \quad x \equiv a_2 \pmod{m_2}, \quad \dots

có nghiệm duy nhất theo modulo $M = m_1 m_2 \cdots m_k$ .

Quy trình ba bước (phương pháp thế liên tiếp)

Với học sinh phổ thông, cách dễ nhất không phải công thức tổng quát mà là ghép từng cặp.

Bước 1 — Viết điều kiện thứ nhất ở dạng tham số. $x \equiv 2 \pmod 3$ nghĩa là $x = 3t + 2$ với $t \in \mathbb{Z}$ .

Bước 2 — Thế vào điều kiện thứ hai, giải theo $t$ .

3t + 2 \equiv 3 \pmod 5 \;\Rightarrow\; 3t \equiv 1 \pmod 5

Nhân hai vế với $2$ (vì $3 \times 2 = 6 \equiv 1 \pmod 5$ , nên $2$ là nghịch đảo của $3$ ):

t \equiv 2 \pmod 5 \;\Rightarrow\; t = 5s + 2

Bước 3 — Thế ngược lại. $x = 3(5s+2) + 2 = 15s + 8$ , tức $x \equiv 8 \pmod{15}$ . Còn điều kiện thứ ba thì lặp lại đúng quy trình với $x = 15s + 8$ .

Ba lưu ý

Điều kiện nguyên tố cùng nhau là bắt buộc. Hệ $x \equiv 1 \pmod 4$ và $x \equiv 2 \pmod 6$ vô nghiệm, vì $\gcd(4,6)=2$ mà hai vế đòi $x$ vừa lẻ vừa chẵn. Luôn kiểm $\gcd$ trước khi giải.
Nghịch đảo modulo có thể tìm bằng thử. Với số nhỏ, chỉ cần thử $1, 2, 3, \dots$ cho tới khi tích đồng dư $1$ . Không cần thuật toán Euclid mở rộng ở mức phổ thông.
Đáp số phải trả về đúng dạng đề hỏi. Hỏi "số nhỏ nhất" thì lấy đại diện dương nhỏ nhất; hỏi "có bao nhiêu số có ba chữ số" thì đếm các $x = 15s+8$ nằm trong $[100; 999]$ .

Phần 3. Bài toán thực chiến

Đề. Một số tự nhiên $n$ chia $3$ dư $2$ , chia $5$ dư $3$ , chia $7$ dư $2$ . Số $n$ nhỏ nhất là A. 23 B. 53 C. 8 D. 68

Cách 1 — Liệt kê và dò

Các số chia 3 dư 2: $2, 5, 8, 11, 14, 17, 20, 23, 26, \dots$ Trong đó chia 5 dư 3: $8, 23, 38, 53, 68, \dots$ Trong đó chia 7 dư 2: thử $8$ (dư 1, loại), $23$ (dư 2 ✓).

Đáp án A. Mất khoảng 15 phép thử.

Điểm yếu. Chạy được vì số nhỏ. Đổi đề thành "chia 11 dư 4, chia 13 dư 7, chia 17 dư 5" thì chu kỳ chung là $2431$ và liệt kê là bất khả thi trong phòng thi.

Cách 2 — Ghép từng cặp bằng CRT

Ghép hai điều kiện đầu. Từ phần 2 ta đã có:

n \equiv 8 \pmod{15}

Ghép tiếp điều kiện thứ ba. Đặt $n = 15s + 8$ và thay vào $n \equiv 2 \pmod 7$ :

15s + 8 \equiv 2 \pmod 7

Rút gọn: $15 \equiv 1 \pmod 7$ và $8 \equiv 1 \pmod 7$ , nên

s + 1 \equiv 2 \pmod 7 \;\Rightarrow\; s \equiv 1 \pmod 7 \;\Rightarrow\; s = 7u + 1

Thế ngược. $n = 15(7u+1) + 8 = 105u + 23$ .

\boxed{n \equiv 23 \pmod{105}}

Số nhỏ nhất là $23$ — đáp án A. Và ta còn biết thêm: mọi nghiệm đều có dạng $23 + 105u$ , điều mà cách liệt kê không cho biết.

	Liệt kê	CRT ghép cặp
Số phép tính	~15 lần thử, tăng nhanh theo số chia	2 lần giải đồng dư bậc nhất
Khi số chia lớn	không dùng được	không đổi độ khó
Cho ra dạng tổng quát	không	có: $n \equiv 23 \pmod{105}$
Trả lời được "có bao nhiêu số 3 chữ số"	phải liệt kê tiếp	đếm ngay: $\lfloor (999-23)/105 \rfloor + 1 = 10$

⭐ Mẹo rút gọn trước khi giải. Ở bước ghép thứ hai, việc thay $15$ bằng $1$ và $8$ bằng $1$ (mod 7) biến một đồng dư trông cồng kềnh thành $s+1 \equiv 2$ . Luôn rút gọn hệ số theo modulo trước, đừng nhân ra.

Phần 4. Góc giáo viên

CRT hợp với định hướng phát triển năng lực tư duy và lập luận toán học: học sinh phải chuyển một phát biểu ngôn ngữ ("chia 3 dư 2") sang ký hiệu, rồi thao tác trên ký hiệu đó.

Bắt đầu bằng hình lưới số. Cho học sinh tự tô màu các số chia 3 dư 2 và chia 5 dư 3 trên dãy $0$ – $29$ , rồi hỏi chu kỳ trùng nhau là bao nhiêu. Định lý trở thành một điều các em tự thấy.
Dùng bài toán Hàn Tín điểm binh làm bối cảnh mở đầu — nó vừa có tính lịch sử vừa cho thấy toán học giải quyết một vấn đề thật.
Cho một phản ví dụ ngay từ đầu: hệ $x \equiv 1 \pmod 4$ , $x \equiv 2 \pmod 6$ . Học sinh thử mãi không ra, rồi mới hiểu vì sao điều kiện nguyên tố cùng nhau không phải chi tiết phụ.

Bẫy cần nhắc. Thứ nhất, quên kiểm $\gcd$ và giải một hệ vô nghiệm. Thứ hai, tìm được $x \equiv 23 \pmod{105}$ rồi trả lời $105$ thay vì $23$ . Thứ ba, đề hỏi "số tự nhiên nhỏ nhất" mà học sinh đưa ra số âm hoặc $0$ khi đại diện lớp đồng dư là $0$ .

Phần 5. Bài tập tự luyện

Bài 1. Tìm số tự nhiên nhỏ nhất chia $4$ dư $3$ và chia $9$ dư $5$ .

Gợi ý: $x = 4t+3$ , thế vào: $4t+3 \equiv 5 \pmod 9 \Rightarrow 4t \equiv 2 \pmod 9$ . Nghịch đảo của $4$ mod $9$ là $7$ (vì $28 \equiv 1$ ), nên $t \equiv 14 \equiv 5 \pmod 9$ . Đáp án: $x = 23$ , tổng quát $x \equiv 23 \pmod{36}$ .

Bài 2. Có bao nhiêu số tự nhiên có ba chữ số chia $5$ dư $1$ và chia $8$ dư $3$ ?

Gợi ý: ghép hai điều kiện được $x \equiv 11 \pmod{40}$ . Đếm các số dạng $40k+11$ trong khoảng $[100; 999]$ . Đáp án: 23 số (từ $131$ đến $971$ ).

Số học đồng dư là mảng mà một bước rút gọn sai kéo theo sai toàn bộ, nên học sinh cần được biết mình lệch ở đâu ngay khi còn nhớ mình đã nghĩ gì. Thầy cô có thể dựng bộ đề luyện đúng dạng này trên Grade: chấm tự động khi nộp kèm lời giải chi tiết từng câu, và theo dõi tiến bộ của từng em qua các lần luyện. Dùng thử miễn phí tại đây.