Theo tài liệu cỗ của Trung hoa, thì bài toán sau đây được đề nghị bởi Sun Tsu Susan-Ching  ở thế kỷ thứ tư sau CN:

“Có một số vật mà người ta chưa biết bao nhiêu. Người ta chỉ biết là nếu chia số
vật đó cho 3 thì còn dư 2, chia cho 5, còn dư 3 và chia cho 7, còn dư 2. Hỏi vậy số
đó ít nhất là bao nhiêu?”.

Trong bộ sách cỗ Ấn độ “Brahma-Sphuta-Siddhanta” (Hệ thống đúng của Brahma) do Brahmagupta (sinh năm 598 sau CN) viết, có nhắc đến một bài toán tương tự như sau:

 “Một bà già đi chợ với một rổ trứng, không may rổ trứng bị một con ngựa dẩm
lên nát bấy. Người chủ ngựa đề nghị đền bù thiệt hại và hỏi bà già có bao nhiêu
trứng trong rổ. 

Bà già quên bẳng số trứng trong rổ. Bà chỉ còn nhớ là khi bà lấy trứng ra từng
cặp thì còn dư 1 trứng trong rổ. Giống như  vậy, khi bà lấy trứng ra từng 3, 4, 5
và 6 trứng mỗi lần, cũng còn dư 1 trứng trong rổ. Tuy nhiên, nếu bà lấy ra 7
trứng mỗi lần thì sau cùng  không còn quả trứng nào trong rổ.

Hỏi vậy, có ít nhất là bao nhiêu trứng trong rổ của bà già?”.

Ngày nay, những bài toán tương tự như những bài toán trên, như bài toán “Hàn Tin điểm binh” (Xem Việt Luận Mừng Xuân Nhâm Thìn 2012,  trang 138), được gọi chung là “Bài toán dư số của người  Trung hoa” (Chinese Reminder Problem).

Thuận Hoà đề nghị cùng độc giả giải 2 bài toán dư số vừa nêu trên.

Bài toán thứ nhất.

Gọi N là số vật phải tìm. N có dư số 2, 3, 2 khi lần lượt chia cho 3, 5 và 7.
N có thể viết là tổng số của 2 số N1 và N2 với N1 chia đúng cho 3, 5 và 7
=>  N1 = bsc(3,5,7) = 3x5x7k  = 105 k          (1)
với  k là một số nguyên bất kỳ, k có thể âm.

N2  là tổng số của 3 số M1, M2 và M3
–   M1  chia đúng cho 5 và 7 nhưng khi chia cho 3 thì cho dư số 2  = >  M1 = bsc(5,7) = 35m,
m là 1 số nguyên được chọn sao cho M1 có dư số bằng 2 khi chia cho 3
–   M2  chia đúng cho 3 và 7 nhưng khi chia cho 5 thì cho dư số 3  =>   M2 = bsc(3,7) = 21n,
n là 1 số nguyên được chọn sao cho M2có dư số bằng 3 khi chia cho 5
–   M3 chia đúng cho 3 và 5 nhưng khi chia cho 7 thì cho dư số 2  =>   M3 = bsc(3,5) = 15p,
p là 1 số nguyên được chọn sao cho M3 có dư số bằng 2 khi chia cho 7

= >   N2  =  M1 + M2 + M3 = 35m + 21n + 15p      (2)

m, n, p  là 3 số nguyên được chọn sao cho dư số của N2 khi chia cho 3, 5 và 7 lần lượt là
2, 3 và 2.

Vì 21 và 15 chia đúng cho 3, nên dư số của N2 khi chia cho 3 chính là dư số của M1 chia cho 3.
Nếu chọn m = 1 thì 35m = 35m = 33 + 2 = bs(3) + 2  => dư số của N2 khi chia cho 3 = 2

Tương tự,  dư số của N2 khi chia cho 5 chính là dư số của M2 chia cho 5
Nếu chọn n = 3 thì 21n = 63 = 60 + 3 = bs(5) + 3 => dư số của N2 khi chia cho 5 = 3

Dư số của N2 khi chia cho 7 chính là dư số của M3 chia cho 7
Nếu chọn p = 2 thì 15p = 30 = 28 + 2 = bs(7) + 2 => dư số của N2 khi chia cho 7 = 2

Với   m = 1, n = 3 và p = 2, suy ra:  N2 = 35 + 21×3 + 15×2 = 128

Tóm lại,  N = N1 + N2 = 105k + 128

Số N nhỏ nhất khi k = -1  =>  N =  108 – 105 = 23.        Đó là lời giải của bài toán thứ nhất.

Bài toán thứ hai.

Gọi N là số quả trứng trong rổ. N, khi chia cho 2, 3, 4, 5 và 6, đều có dư số là 1.

=>   N-1 là bội số chung của 2, 3, 4, 5 và 6

= >  N – 1 = bsc(2,3,4,5,6)  =  4x3x5k  = 60k  =>  N =  60k + 1        (1),

N chia đúng cho 7  =>  N =  7h,         (2)

Suy ra:  7h  =  60k + 1            (3)

k và h là 2 số nguyên phải chọn sao cho (3) được nghiệm đúng.

Nghiệm của phương trình (3) có thể tìm được bằng cách tìm những trị số k sao cho

60k + 1 cũng là bội số của 7.

Phương trình (2) được nghiệm đúng với    h = 43    và      k = 5.

Theo (2),  N = 7h = 7 x 43 = 301.  Đó là nghiệm của bài toán thứ hai.

Thuận Hoà