Định Lý Số Dư Trung Hoa: Giải Bài Toán Cổ và Hiện Đại

by Thầy Đông · January 9, 2026

Rate this post

Bài toán tìm một số khi biết số dư khi chia cho các số khác nhau là một dạng toán cổ xưa, xuất hiện trong nhiều nền văn minh. Một trong những ví dụ nổi tiếng nhất là điển tích về Hàn Tín điểm binh. Trong một lần hành quân, danh tướng Hàn Tín đã dùng phương pháp độc đáo để xác định chính xác số lượng binh lính của mình. Ông cho binh lính xếp thành các hàng có số lượng lần lượt là 3, 5 và 7. Số quân còn dư ra sau mỗi lần xếp hàng đã giúp ông tính toán ra tổng số binh lính. Cụ thể, khi xếp hàng 3 thì dư 2, xếp hàng 5 thì dư 3, và xếp hàng 7 thì dư 5. Từ những dữ kiện này, Hàn Tín đã suy luận ra rằng ông có tổng cộng 68 binh lính. Đây chính là một ứng dụng thực tế của Định lý Số dư Trung Hoa. Bên cạnh đó, trong tác phẩm “Anh Hùng Xạ Điêu”, Hoàng Dung đã thách đố Anh Cô giải bài toán tương tự, được gọi là Quỷ Cốc Toán: “Có một số không biết là bao nhiêu, chia cho ba thì thừa hai, chia cho năm thì thừa ba, chia cho bảy thì thừa hai, hỏi là bao nhiêu?”. Các bài toán này đều có thể được giải quyết một cách hiệu quả bằng Định lý Số dư Trung Hoa, một công cụ mạnh mẽ trong lĩnh vực số học modulo.

Đề Bài

“Điển tích Trung Quốc kể rằng ngày xưa danh tướng Hàn Tín có khả năng tính chính xác số binh lính của mình bằng cách: cho binh lính lần lượt xếp thành hàng 3, hàng 5, hàng 7, rồi lấy số binh lính dư ra ở mỗi cách xếp hàng để tính ra được số lính. Cụ thể, binh lính xếp hàng 3 thì dư 2 người, xếp hàng 5 thì dư 3, xếp hàng 7 thì dư 5. Ông liền tính ngay ra được binh lính có tổng cộng 68 người. Đây là bài toán Hàn Tín điểm binh.

Một điển tích khác nằm trong truyện Anh Hùng Xạ Điêu của Kim Dung, đoạn Hoàng Dung và Quách Tĩnh gặp Thần toán tử Anh Cô tại Đầm tối, lúc rời đi Hoàng Dung có ra 3 đề toán cho Anh Cô, và bảo rằng Anh Cô trong vòng nửa năm nhất định không giải ra được. Trong đó bài số 3 gọi là bài Quỷ Cốc Toán như sau: Có một số không biết là bao nhiêu, chia cho ba thì thừa hai, chia cho năm thì thừa ba, chia cho bảy thì thừa hai, hỏi là bao nhiêu?

Một cách tổng quát, ta có bài toán sau: Tìm số x sao cho:

X equiv a_1 pmod{m_1}

X equiv a_2 pmod{m_2}

[…]

X equiv a_k pmod{m_k}

Đây là một bài toán về số học module mà có thể giải dễ dàng bằng định lý phần dư Trung Hoa (Chinese Remainder Theorem – CRT).”

Phân Tích Yêu Cầu

Các bài toán được trình bày yêu cầu chúng ta tìm một số nguyên X thỏa mãn đồng thời nhiều điều kiện đồng dư tuyến tính. Cụ thể, khi chia X cho từng số nguyên dương m_i (trong các ví dụ là 3, 5, 7), ta luôn nhận được số dư tương ứng là a_i. Yêu cầu chính là xác định giá trị cụ thể của X, hoặc một dạng tổng quát của X nếu có nhiều nghiệm.

Kiến Thức/Nền Tảng Cần Dùng

Để giải quyết các bài toán dạng này, chúng ta cần dựa vào Định lý Số dư Trung Hoa (Chinese Remainder Theorem – CRT).

Điều kiện áp dụng Định lý

Định lý Số dư Trung Hoa có thể áp dụng cho một hệ phương trình đồng dư tuyến tính dạng:

$X equiv a_1 pmod{m_1}$
$X equiv a_2 pmod{m_2}$
[…]
$X equiv a_k pmod{m_k}$

với điều kiện các số m_1, m_2, ..., m_k phải đôi một nguyên tố cùng nhau (tức là ước chung lớn nhất của bất kỳ cặp m_i, m_j nào với i ne j đều bằng 1).

Các bước giải theo Định lý Số dư Trung Hoa

Giả sử điều kiện trên được thỏa mãn, chúng ta sẽ tìm nghiệm X theo các bước sau:

Tính tích các mô-đun:
Tính M là tích của tất cả các mô-đun:
$M = m_1 \times m_2 \times \ldots \times m_k$
Tính các tích riêng phần:
Đối với mỗi m_i, tính M_i bằng cách lấy M chia cho m_i:
$M_i = \dfrac{M}{m_i}$
Tính nghịch đảo modulo:
Đối với mỗi i từ 1 đến k, tìm y_i sao cho:
$M_i \times y_i equiv 1 pmod{m_i}$
Số y_i này được gọi là nghịch đảo modulo của M_i theo mô-đun m_i. Việc tìm y_i thường được thực hiện bằng thuật toán Euclid mở rộng.
Xây dựng nghiệm tổng quát:
Nghiệm tổng quát của hệ phương trình đồng dư là:
$X equiv (a_1 M_1 y_1 + a_2 M_2 y_2 + \ldots + a_k M_k y_k) pmod{M}$
Hoặc có thể viết dưới dạng:
$X = a_1 M_1 y_1 + a_2 M_2 y_2 + \ldots + a_k M_k y_k + t \cdot M$
với t là một số nguyên bất kỳ (t in Z).

Hướng Dẫn Giải Chi Tiết

Bây giờ, chúng ta sẽ áp dụng các bước trên để giải hai bài toán đã nêu.

Bài toán 1: Hàn Tín điểm binh

Đề bài cho ta hệ phương trình đồng dư:
$X equiv 2 pmod{3}$
$X equiv 3 pmod{5}$
$X equiv 5 pmod{7}$

Bước 1: Tính tích các mô-đun
Các mô-đun là 3, 5, 7. Chúng đôi một nguyên tố cùng nhau.
$M = 3 \times 5 \times 7 = 105$

Bước 2: Tính các tích riêng phần
$M_1 = \dfrac{M}{m_1} = \dfrac{105}{3} = 35$
$M_2 = \dfrac{M}{m_2} = \dfrac{105}{5} = 21$
$M_3 = \dfrac{M}{m_3} = \dfrac{105}{7} = 15$

Bước 3: Tính nghịch đảo modulo

Tìm y_1 sao cho $35 \times y_1 equiv 1 pmod{3}$ .
Ta có $35 equiv 2 pmod{3}$ . Vậy cần tìm $2 \times y_1 equiv 1 pmod{3}$ .
Nhân cả hai vế với 2: $4 \times y_1 equiv 2 pmod{3}$ , suy ra $y_1 equiv 2 pmod{3}$ . Chọn $y_1 = 2$ .
Tìm y_2 sao cho $21 \times y_2 equiv 1 pmod{5}$ .
Ta có $21 equiv 1 pmod{5}$ . Vậy cần tìm $1 \times y_2 equiv 1 pmod{5}$ .
Chọn $y_2 = 1$ .
Tìm y_3 sao cho $15 \times y_3 equiv 1 pmod{7}$ .
Ta có $15 equiv 1 pmod{7}$ . Vậy cần tìm $1 \times y_3 equiv 1 pmod{7}$ .
Chọn $y_3 = 1$ .

Bước 4: Xây dựng nghiệm tổng quát
Áp dụng công thức:
$X equiv (a_1 M_1 y_1 + a_2 M_2 y_2 + a_3 M_3 y_3) pmod{M}$
$X equiv (2 \times 35 \times 2 + 3 \times 21 \times 1 + 5 \times 15 \times 1) pmod{105}$
$X equiv (140 + 63 + 75) pmod{105}$
$X equiv 278 pmod{105}$

Để tìm giá trị cụ thể, ta thực hiện phép chia lấy dư:
$278 = 2 \times 105 + 68$
Do đó, $X equiv 68 pmod{105}$ .

Nghiệm tổng quát là $X = 68 + 105t$ , với $t in Z$ .
Nếu chọn $t=0$ , ta có $X = 68$ , khớp với kết quả trong điển tích.

Bài toán 2: Quỷ Cốc Toán

Đề bài cho hệ phương trình đồng dư:
$X equiv 2 pmod{3}$
$X equiv 3 pmod{5}$
$X equiv 2 pmod{7}$

Lưu ý: Bài toán này có hai điều kiện đồng dư giống nhau (dư 2 khi chia cho 3 và dư 2 khi chia cho 7).

Bước 1: Tính tích các mô-đun
Các mô-đun là 3, 5, 7. Chúng đôi một nguyên tố cùng nhau.
$M = 3 \times 5 \times 7 = 105$

Bước 2: Tính các tích riêng phần
$M_1 = \dfrac{M}{m_1} = \dfrac{105}{3} = 35$
$M_2 = \dfrac{M}{m_2} = \dfrac{105}{5} = 21$
$M_3 = \dfrac{M}{m_3} = \dfrac{105}{7} = 15$

Bước 3: Tính nghịch đảo modulo

Tìm $y_1$ sao cho $35 \times y_1 equiv 1 pmod{3}$ .
$35 equiv 2 pmod{3}$ . Ta có $2 \times y_1 equiv 1 pmod{3}$ . Chọn $y_1 = 2$ .
Tìm $y_2$ sao cho $21 \times y_2 equiv 1 pmod{5}$ .
$21 equiv 1 pmod{5}$ . Ta có $1 \times y_2 equiv 1 pmod{5}$ . Chọn $y_2 = 1$ .
Tìm $y_3$ sao cho $15 \times y_3 equiv 1 pmod{7}$ .
$15 equiv 1 pmod{7}$ . Ta có $1 \times y_3 equiv 1 pmod{7}$ . Chọn $y_3 = 1$ .

Bước 4: Xây dựng nghiệm tổng quát
Áp dụng công thức:
$X equiv (a_1 M_1 y_1 + a_2 M_2 y_2 + a_3 M_3 y_3) pmod{M}$
$X equiv (2 \times 35 \times 2 + 3 \times 21 \times 1 + 2 \times 15 \times 1) pmod{105}$
$X equiv (140 + 63 + 30) pmod{105}$
$X equiv 233 pmod{105}$

Thực hiện phép chia lấy dư:
$233 = 2 \times 105 + 23$
Do đó, $X equiv 23 pmod{105}$ .

Nghiệm tổng quát là $X = 23 + 105t$ , với $t in Z$ .
Nếu chọn $t=0$ , số cần tìm là 23.

Mẹo kiểm tra:

Với X=23:
- $23 div 3 = 7$ dư 2. (Đúng)
- $23 div 5 = 4$ dư 3. (Đúng)
- $23 div 7 = 3$ dư 2. (Đúng)

Lỗi hay gặp:

Sai sót khi tính nghịch đảo modulo, đặc biệt với các số lớn.
Nhầm lẫn giữa frac và dfrac, hoặc thiếu dấu .
Không kiểm tra xem các mô-đun có nguyên tố cùng nhau hay không trước khi áp dụng định lý. Nếu không, cần sử dụng thuật toán tổng quát hơn.

Đáp Án/Kết Quả

Đối với bài toán Hàn Tín điểm binh, số binh lính là 68.
Đối với bài toán Quỷ Cốc Toán, số nguyên cần tìm có dạng $X = 23 + 105t$ , với nghiệm nhỏ nhất là 23.

Kết Luận

Định lý Số dư Trung Hoa là một công cụ toán học mạnh mẽ, không chỉ giải quyết các bài toán đố cổ xưa mà còn có ứng dụng rộng rãi trong mật mã học, khoa học máy tính và các lĩnh vực đòi hỏi xử lý số học modulo. Việc hiểu rõ các bước áp dụng định lý, từ việc xác định điều kiện đến tính toán các thành phần và xây dựng nghiệm, giúp chúng ta chinh phục các bài toán tưởng chừng phức tạp này một cách hệ thống và chính xác.

Ngày chỉnh sửa nội dung mới nhất January 9, 2026 by Thầy Đông

Thầy Đông

Thầy Đông – Giảng viên Đại học Công nghiệp Hà Nội, giáo viên luyện thi THPT
Thầy Đông bắt đầu sự nghiệp tại một trường THPT ở quê nhà, sau đó trúng tuyển giảng viên Đại học Công nghiệp Hà Nội nhờ chuyên môn vững và kinh nghiệm giảng dạy thực tế. Với nhiều năm đồng hành cùng học sinh, thầy được biết đến bởi phong cách giảng dạy rõ ràng, dễ hiểu và gần gũi. Hiện thầy giảng dạy tại dehocsinhgioi, tiếp tục truyền cảm hứng học tập cho học sinh cấp 3 thông qua các bài giảng súc tích, thực tiễn và giàu nhiệt huyết.