Lời nói đầu

Tháng 3 năm 2011, trong trang nhà http://www.edu.go.vn/e-tap-chi/, tác giả “nhungnghiloc4”  có trình bày lại lời giải bài toán “Hàn Tín điểm binh” của GS Hoàng xuân Hãn viết từ năm 1943. Lời giải nầy cũng đã được TS Trần đình Viện nhắc lại và bổ sung vào tháng 2 năm 2007 trong trang nhà http://static.khoia0.com/.

Theo TS Viện, thì lời giãi của GS Hoàng xuân Hãn có chỗ không được rõ ràng và ông đã bổ sung lời giải đó bằng cách áp dụng ký hiệu “mod” (Modulo) và những tính chất liên quan đến ký hiệu đó. Thuận Hoà xin mở ngoặc để nhắc lại định nghĩa và 2 tình chất căn bản của Modulo:

“mod” là ký hiệu để viết dư số của phép chia của một số với một số khác. Nếu chia số N cho số q và được dư số r, thì ta có thể viết:  N = r (mod q), thí dụ:  47 =  2 (mod 3). Hai tính chất căn bản của Modulo là
              N = r (mod q),  N’ = r’ (mod q) 
=>         N + N’ = (r + r’) (mod q)   và   N.N’ = r.r’ (mod q)

Thí dụ:   28 = 3 (mod 5),  21 = 1 (mod 5)
                   =>  28 + 21 =  (3 + 1) (mod 5)  =>     49 =  4 (mod 5)  
                          28 x 21 =    3 x 1  (mod 5)   =>  588 =  3 (mod 5)
Đóng ngoặc.

Theo nhận xét của Thuận Hoà thí lời giải của GS Hoàng xuân Hãn có hơi dài dòng (?) và lời giải dùng ký hiệu Modulo của TS Trần đình Viện có lẽ  thích hợp với người có trình độ đại học mà thôi (?).

Trong phần dưới đây, Thuận Hoà trước hết trình bày lại lời giải của GS Hoàng xuân Hãn như đã viết trong bài “Bổ sung cách giải bài toán ‘Hàn Tín điểm binh của GS Hoàng Xuân Hãn’ “của TS Trần đình Viện. Sau đó, Thuận Hoà sẽ có lời bàn thêm, cố gắng sao cho đơn giản để thích hợp với đại đa số độc giả của báo chí hàng ngày.

*     *     *

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. 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

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:

Ông 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 và 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 đã 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)

 *     *     *

Sau đây là lời bàn thêm của Thuận Hoà.

Nếu số N chia đúng cho 3, 5 và 7, thì N phải là một bội số chung bất kỳ của 3, 5 và 7. Bội số chung nhỏ nhất của 3, 5 và 7 là 3x5x7 = 105.
Mộti bội số chung bất kỳ của 105 có dạng:

N =  105k        với  k  là một số nguyên bất kỳ.

Nếu bạn phải tìm một số N mà khi chia cho 3 có dư số là a, khi chia cho 5 có dư số là b và chia cho 7 có dư số là c, thì số đó có thể có dạng như thế nào?

Trước hết số đó có thể gồm có 2 phần: phần đầu là một số chia đúng cho cả 3 số 3, 5 và 7 và phần sau là phần sẽ cho các dư số khi chia cho 3, 5 và 7, tức là:

            N  =  N1  +  N2

Theo trên, phần thứ nhất có dạng tổng quát:
            N1  = 105k      k  là một số nguyên bất kỳ

Phần thứ hai N2  là số cho các dư số a, b và c khi lần lượt chia cho 3, 5 và 7.
Ta có thể phân tích N2 thành tổng số của 3 số hạng:

            N2  = bsc(5,7)x + bsc(3,7)y + bsc(3,5)z     

với     bsc(5,7): bội sô chung của 5 và 7, vv …

Ta có:  bsc(5,7) = 5x7m = 35m,  bsc(3,7) = 3x7n = 21n, bsc(3,5) = 3x5p = 15p
với  m, n, p  là mhững số nguyên bất kỳ.

=>        N2 = 35m x + 21n y + 15p z               (1)

Số hạng thứ nhất sẽ cho dư số a khi chia N2 cho 3, số hạng thứ hai cho dư số b khi chia N2 cho 5 và số hạng thứ ba cho dư số c khi chia N2 cho 7.  Ba thông số m, n và p có thể điều chỉnh để có những dư số trong ba số hạng lần lượt bằng x, y và z.

Dư số của N2 chia cho 3         (để ý rằng 15 vả 21 chia đúng cho 3):
         =  Dư số của 70x chia cho 3 = x  (chọn m = 2)     vì 70x = (bs3  + 1)x  =>  x  = a
Dư số của N2 chia cho 5         (để ý rằng 35 vả 15 chia đúng cho 5):
         =  Dư số của 21y chia cho 5 = y  (chọn n = 1)    vì 21y = (bs5 +  1)y   =>  y = b
Dư số của N2 chia cho 7         (để ý rằng 35 vả 21chia đúng cho 7):
         =  Dư số của 15z chia cho 7 = z  (chọn p = 1)     vì  15z = (bs7 + 1)z   =>  z = c

Tóm lại, m = 2,  n = 1  và  p = 1,  ta có  x = a,  y = b  và  z = c

(1) =>  N2  =  70a  +  21b  + 15c

=>        N  =  N1  + N2 

Bài toán Hàn Tín điểm binh suy rộng

Tìm số N có dư số a khi chia cho 3, b khi chia cho 5, c khi chia cho 7 và d khi chia cho 11.

Lý luận như trên, ta có:

            N     =   N1  + N2

với       N1   =  3x5x7x11 k = 1,155k  với   k  là một số nguyên bất kỳ
            N2   =  bsc(5,7,11)x +  bsc(3,7,11)y + bsc(3,5,11)z + bsc(3,5,7)u

Ta có:  bsc(5,7,11) = 5x7x11m = 385m,         bsc(3,7,11) = 3x7x11n = 231n
            bsc(3,5,11) = 3x5x11p  = 165p,          bsc(3,5,7)   =  3x5x7q  =  105q

Bốn thông số m, n, p, q là các số nguyên bất kỳ.

=>        N2   =   385m x  +  231n y  +  165p z  +  105q u       (2)

Số hạng thứ nhất sẽ cho dư số a khi chia N2 cho 3, số hạng thứ hai cho dư số b khi chia N2 cho 5, số hạng thứ ba cho dư số c khi chia N2 cho 7 và số hạng thứ tư cho dư số d khi chia N2 cho 11.  Bốn  thông số m, n, p và q có thể điều chỉnh để có những dư số trong bốn số hạng lần lượt bằng x, y, z và u..

Dư số  của N2 chia cho 3    = Dư số của 385x chia cho 3    (chọn m= 1)
                                        = x   vì  385x = (384 + 1)x = (bs3 + 1)x      =>   x = a
 Dư số  của N2 chia cho 5    = Dư số của 231y chia cho 5       (chọn n = 1)
                                        = y   vì  231y = (230 + 1)y = (bs5 + 1)y      =>   y = b
 Dư số  của N2 chia cho 7  = Dư số của 330z chia cho 7        (chọn p = 2)
                                        = z   vì  330z = (329 + 1)z = (bs7 + 1)z        =>  z  = c
Dư số  của N2 chia cho 11  = Dư số của 1,365 chia cho 11   (chọn q = 13)
                                        = u   vì  1,365u = (1,364 + 1)u = (bs11 + 1)u    =>  u = d

Suy ra:  với  m = 1,  n = 1,  p = 2  và  q = 13, ta có  x = a, y = b, z = c  và  u = d

(2)    =>       N2 = 385a + 231b + 330c + 1,365d

=>        N   =  N1  + N2  = 1,155k + 385a + 231b + 330c + 1,365d
              với  k  là số nguyên bất kỳ

Nhân xuân Nhâm Thìn sắp đến, Thuận Hoà xin kính chúc quí độc giả một năm mới An Khang Thịnh Vượng và Hạnh Phúc tràn đầy.

Thuận Hoà