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.
Hà nội 18/2/2007
TS. Trần Đình Viện
Comments are closed.