ĐẶT
VẤN ĐỀ
Báo Khoa Học số 13 và 14 ra tháng 1 và 2 năm
1943 có bài “ Hàn Tín điểm binh “ của gs Hoàng Xuân Hãn. Một bài toán số học
lý thú, được lưu truyền từ lâu. Chúng tôi giới thiệu lại bài toán đó cùng
cách giải của tác giả HOÀNG XUÂN HÃN đồng thời giải thích thêm vài chỗ trong
lập luận với hy vọng đỡ khó khăn hơn cho bạn đọc.
BÀI TOÁN, Tục truyền rằng (*), ngày xưa, Hàn
Tín danh tướng của Lưu Bang (Hán Cao Tổ) điểm binh theo cách sau đây: bảo
lính xếp hàng ba, hàng năm, hàng bẩy rồi ghi các số lẻ tương ứng sẽ suy ra
số lính bằng cách sau đây:
Nhân số lẻ hàng ba cho 70, số lẻ hàng năm cho
21, nhân số lẻ hàng bẩy cho 15. Cộng các kết quả ấy lại. Thêm số đó với một
bội số thich hợp của 105 sẽ được số lính
Nếu ký hiệu số lính là S, số lẻ xếp hàng 3,
hàng 5, hàng 7 tương ứng là a, b, c.
thì S = 70.a + 21.b + 15.c + 105.k
(k là số nguyên chọn thích hợp với số lính
của một đại đội, một tiểu đoàn hay trung đoàn...)
CHỨNG MINH
Bài toán trên được đặt ra như sau: Tìm số S
sao cho khi chia S cho 3, cho 5, cho 7 thi số dư tương ứng là a, b, c . (a,
b, c, S đều là các số tự nhiên, a < 3, b < 5,
c < 7. Hoăc có thể viết:
S = 3A + a
S = 5B + b
S = 7C + c
Nhân hai vế đẳng thức đầu với 5.7.m (35m) ;
được
35.m.S = 105.m.A + 35.m.a.
Nhân hai vế của đẳng thức thứ hai với 3.5.n ;
được
21.n.S = 105.n.B + 21.n.b
Nhân hai vế của đẳng thức thứ ba với 3.5.p
được
15.p.S = 105.p.c
Cộng 3 đẳng thức mới được
(35m + 21n + 15p)S =
105(mA + nB + pC) + 35ma + 21nb + 15pc (1)
Ta sẽ tìm ba số nguyên m, n. p nghiệm đẳng
thức sau này:
35m + 21n + 15p = 105k + 1 (2)
(chỗ này HOÀNG XUÂN HÃN không giải thích tại
sao phải có đẳng thức (2))
Ta viết (2) như sau
35m - 1 = 3(35k - 7n - 5p)
Thế tỏ ra vế đầu chia đúng cho 3 . Ví dụ m là
2 thì có
35.2
- 1 = 3. 23
Trừ hai đẳng thức trên, ta sẽ thấy:
35(m - 2) = 3D
Vế đầu chia 3 đúng, nhưng 35 không chia cho 3 đúng.
Vởy m - 2
chia cho 3 đúng.
Và m = 2 + 3M .
Tương tự ta tìm được
n = 1 + 5N và p = 1 + 7P
Làm như thế, ta tìm được vô số m, n, p nghiệm
đẳng thức (2).
Cho M = N = P = 0, ta được ba số m = 2, n =
1, p = 1 gọn nhất.
Thay nó vào đẳng thức (1) ta sẽ thấy:
(105 + 1) S = 105 (2A + B +
C) + 70a + 21b + 15c
Hay là:
S = 105 T + (70a + 21b + 15c).
Vậy số S bằng 70a + 21b + 15c rồi thêm bớt
một bội số của 105.
Đó là quy tắc “ Hàn Tín điểm binh “ mà HOÀNG
XUÂN HÃN dã chứng minh. Sau đây chúng tôi sẽ bổ sung thêm vài cách chứng
minh quy tắc đó
Cách 1. Gọi S là số TN thỏa mãn điều kiện
chia cho 3, 5, 7 thì được số dư tương ứng là a, b, c. S không duy nhất mà
sai khác một bội số của 105. Thực vậy nếu S1 thỏa mãn đk của bài toán thì S2
= S1 + 105.k (k là sớ tự nhiênh bất kỳ) cũng thỏa mãn đk của bài toán. Vì
vậy S có dạng
S = 105k + h , h là số nhỏ nhất thỏa mãn đk
chia cho 3 dư a, chia cho 5 dư b chia cho 7 dư c. Vậy h phải có dạng:
h = h1 + h2 + h3 . Trong đó h1 là số bé
nhất chia hết cho 5, 7 nhưng chia cho 3 dư a ; h2 là số bé nhất chia hết cho
3, 7, nhưng chia cho 5 dư b . h3 là số bé nhất chia hết cho 3, 5, nhưng chia
cho 7 dư c . Ta lần lượt tìm các số h1, h2, h3
h1 có dạng:
h1 = 35.m , chọn số bé nhất m để (35m - a) chia hết cho 3 ;
35 không phải là bội của a nên m là một bội số của a: m = m’.a .
(35m - a) =
(35.m’ - 1) a là bội số của 3 suy ra (35m’ - 1) chia hết cho 3.
Số nhỏ nhất m’ để
(35.m’ - 1) chia hết cho 3 là 2 ; m = 2a .
Suy ra h1 = 70.a thỏa mãn yêu cầu nói trên.
Tương tự ta tìm được
h2 = 21b và h3 = 15p
Vậy
S = 105k + 70a + 21b + 15c
Cách 2. Để dễ dàng trong lập luận chứng minh
của HOÀNG XUÂN HÃN, ta đưa vào quan hệ mod(k) giữa các số nguyên s, s’ như
sau:
Định nghĩa Ta gọi s, s’ cùng mod(k) hoặc s =
s’mod(k) nếu s-s’ chia hết cho k
Suy ra: Nếu u = u’mod(k), v = v’mod(k)
thì (u + v) = (u’ + v’)mod(k) ; u. v = u’v’mod(k)
Trở lại chứng minh quy tắc Hàn Tín của HOÀNG
XUÂN HÃN (giải thích tại sao có đẳng thức (2))
Từ dẳng thức (1) (35m + 21n + 15p).S = 105k +
(35ma + 21nb + 15pc) (1)
Ký hiệu u = 35m + 21n +15pc , v = 35ma + 21nb
+ 15pc, (1) được viết
u S = vmod(105) (1’). Nếu tìm đựơc các số
nguyên m, n, p sao cho
u = 1mod(105) (3) thì S có thể viết S =
v.mod(105)
Tìm m, n, p thỏa mãn (3) như sau:
u = 35m + 21n + 15p = 1 + 105k hoặc 35m - 1
= 105k -21n - 15p (4)
Vế phải của (4) chia hết cho 3 nên vế trái
cũng chia hết cho 3. Dễ dàng tìm được m = 2 là số nguyên dương nhỏ nhất để
(35m - 1) chia hết cho 3.
Tương tự ta tìm được n = 1, p = 1 là các số
nguyên dương nhỏ nhất thỏa mãn (4).
Vậy
S = 105.k + (70a + 21b + 15p)
Quy tắc trên được tóm tắt trong bốn câu thơ
của Trình Đại Vỹ đời nhà Minh sau đây:
Tam nhân đồng hành thất thập hy
Ngũ thụ mai hoa trấp nhất chi.
Thất tử đoàn viên chính bán nguyệt
Trừ bách linh ngũ tiện đắc tri
Dịch
Ba người cùng đi ít bẩy mươi
Năm cõi mai hoa hăm mốt cành
Bẩy gã xum vầy vừa nửa tháng.
Trừ trăm linh năm biết số thành. (Bài thơ
chữ Hán do HOÀNG XUÂN HÃN sưu tầm và dịch)
MỞ RỘNG QUY TẮC HÀN TÍN
Tìm số tự nhiên S sao cho khi chia S lần
lượt cho các số nguyên tố p1, p2, p3, .
được số dư tương ứng là q1, q2, q3, . .
S = p1p2p3. k + p2p3q1m1 + p3p1q2m2 +p1p2q3
m3
Trong đó m1, m2, m3 là các số tự nhiên nhỏ
nhất sao cho
(p2p3m1 -1), (p3p1m2 - 1), (p1p2m3 - 1) theo
thứ tự chia hết cho p1, p2, p3.
____________________
(*) Theo HOÀNG XUÂN HÃN bài toán này chép ở
sách Tôn Tử toán kinh, từ thời Hậu Hán, Bài toán có nhiều tên khác nhau qua
các triều đại . Đến đời Minh, Trình Đại Vỹ mới gọi là “ Hàn Tín điểm binh “.
Không chắc Hàn Tín có điểm binh theo cách đó không.
Trần
Đình Viện
viendinhtran2006@yahoo.com
|