ĐỌC VUI VÀ SUY NGHĨ

Cổ vũ lòng yêu thích các trò chơi hữu ích cho sự luyện tập trí óc trong cộng đồng người Việt

KQNC05 – Bàn thêm về phương trình Diophantine

Nếu mời bạn giải bài toán cổ điển sau đây: “Gà và chó” nhốt chung 1 chuồng và có số chân bằng 42. Hỏi vậy có bao nhiêu gà và bao nhiêu chó?”, bạn sẽ trả lời ngay là “không được, bài toán không đủ giả thiết để giải”.  Bạn đã nghĩ đúng, vì nếu gọi x và y lần lượt là số gà và số chó thì bạn chỉ có một phương trình:

          2x + 4y = 42   hay   x + 2y = 21   (1)    sau khi đơn giản 2 vế cho 2.         

Bài toán có 2 ẩn số mà chỉ có 1 phương trình thì dĩ nhiên không có lời gỉải! Có phải thế không? Thực ra, bài toán thiếu 1 phương trình nhưng bù lại, nó có thêm một điều kiện, đó là: 2 ẩn số x và y phải là số nguyên và lớn hơn 0. Ngoài ra, còn những giới hạn của các ẩn số x và y: theo phương trình (1) thì x phải nhỏ hơn 21; những điều kiện chẳn lẻ mà phương trình phải thoả mản: vế thứ hai của phương trình (1) là số lẻ, vậy vế thứ nhứt cũng phải là số lẻ, mà 2y là số chẳn, vậy x phải là số lẻ.  Do đó, x (số gà) có thể có những trị số: 1, 3, 5, 7, 9, 11, 13, 15, 17, 19 và y (số chó) = (21-x)/2 có những trị số tương ứng: 10, 9, 8, 7, 6, 5, 4, 3, 2, 1. Tóm lại, bài toán gà và chó đã cho có nhiều lời giải. Nếu bài toán có thêm một phương trình nữa, thí dụ: số đầu trong chuồng là 18, hay x + y = 18, thì bài toán sẽ có một lời giải duy nhứt: x = 15, y = 3.

Bài toán gà và chó trên là một thí dụ đơn giản của một loại phương trình toán học tổng quát hơn gọi là phương trình Diophantine, gọi theo tên của nhà toán học Diophantus ở Alexandra (Ai cập) vào thế kỹ thứ 3. Trong toán học, phương trình Diophantine là một phương trình đa thức không xác định mà ẩn số cũng như các hệ số là những số nguyên dương hay âm. Trong bài toán Diophantine, số phương trình ít hơn số ẩn số và nghiệm số phải là số nguyên dương hay âm. Sau đây là thí dụ của vài phương trình Diophantine:

ax + by  =  c   Phương trình Diophantine tuyến tính (hay bậc nhứt) với 2 ẩn số

x2 + y2   = z2   Phương trình Diophantine bậc hai với 3 ẩn số. Đó là phương trình
                      Pythagore
, có vô số lời giải, mỗi lời giải hợp thành một bộ ba số
                      Pythagore
. Thí dụ: (3,4,5), (5,12,13), (8,15,17), (12,35,37), …
                      Phương trình xn + yn  = zn với n > 2  không có lời giải. Đó là định lý
                      cuối cùng của Fermat
.

x2 – ny2  = 1   với n không phải là bình phương của 1 số nguyên. Đó là Phương
                      trình Pell
, đặt theo tên của nhà toán học người Anh John Pell.
                     Thật ra, phương trình thuộc loại nầy đã được khảo sát từ xưa bởi các
                      nhà toán học cổ Ấn độ, nhứt là Brahmagupta ở thế kỹ thứ 6.  
                     Jayadeva  (thế kỹ thứ 9) và Bhaskara (thế kỹ 12) đã tìm được lời giải
                      đầy đủ của  phương trình 61x2 + 1 = y2.  Đó là x = 226153980  và 
                     y = 1766319049.

Có nhiều bài toán Diophantine chưa giải được cả thế kỷ nay và vẫn còn được các nhà toán học để ý tới.

Phần còn lại của bài viết nầy xin được dành để bàn về cách giải tổng quát những phương trình hay hệ thống phương trìng Diophantine đơn giản nhưng lại có nhiều áp dụng thực tiển nhất. Đó là phương trình Diophantine tuyến tính có 2 ẩn số x và y:

          ax + by  =  c        (2)

hệ thống 2 phương trình Diophantine có 3 ẩn số x, y và z

          ax  +  by + cz  =  u       (3)
        mx +  ny + pz  =  v       (4)

Bài toán giải phương trình (2) hay giải hệ thống phương trình (3) & (4) sẽ được gọi chung là bài toán Diophantine. Các ẩn số x, y, z và các  hệ số a, b, c, m, n, p, u, v là những số nguyên dương hay âm. Điều kiện nầy gọi chung là điều kiện Diophantine. Bài toán Diophantine có một tính chất chung là số phương trình ít hơn số ẩn số một đơn vị.

Một cách đại khái, nếu một ẩn số trong bài toán Diophantine, thí dụ như y trong phương trình (2) hay z trong hệ thống phương trình (3) & (4), có một trị số nào đó, thì bài toán rút lại sẽ có số phương trình bằng số ẩn số, và do đó theo lý thuyết có thể giải được . Có thể, nhưng chưa chắc đã giải được vì các ẩn số còn phải thoả các điều kiện khác như điều kiện Diophantine, điều kiện chia đúng, điều kiện chẳn lẻ của các số hạng, vv… Nếu giải được, thì bài toán có thể có: hoặc (i) một nghiệm số duy nhất, hoặc (ii) nhiều nghiệm số, hoặc (iii) vô số nghiệm số, tuỳ theo các điều kiện của bài toán.

Trong phương trình (2), nếu c = 0, thì phương trình ax + by = 0 có vô số nghiệm số có dạng:
          ax + by = 0 (5)   =>  x = bt, y = – at     (6)     với  t là một số nguyên bất kỳ

Trong hệ thống phương trìng (3) & (4), nếu u = 0 và v = 0, thì hệ thống có thể giải như sau:

          ax  +  by + cz  =  0         (7)
         mx +  ny + pz  =  0        (8)

Nhân (7) cho p và (8) cho c rồi trừ vế để loại z:

          (pa – cm) x + (bp – nc) y = 0        (9)

Theo phương trình (5) thì nghiệm số của (9) là:

          x = (bp – nc) t ,  y = (cm – pa) t   (10)  với t là một số nguyên bất kỳ.

Thay trị số của x và y vào phương trình (7):

          a(bp – nc) t + b(cm – pa) t + cz = 0

Khai triển và rút gọn: 

          z = (an – mb) t               (11)

Như vậy, nếu các vế thứ hai của bài toán Diophantine đều bằng 0, thì bài toán Diophantine có vô số nghiệm số có dạng (6) hay (10) & (11).

Bài toán Diophantine có thể đưa về dạng có các vế thứ hai bằng 0 nếu ta biết được một nghiệm số nào đó của bài toán. Thí dụ bài toán Diophantine có 1 nghiệm số là (x0,y0) cho phương trình (2)

           ax0 + by0  =  c                (12)

và      (x0,y0,z0)    cho hệ thống   (3) & (4):

          ax0  + by0 + cz0  =  u      (13)
         mx0 + ny0 + pz0  = v       (14)

Trừ vế (2) với 12):         

          a(x – x0) + b(y – y0)  =  0

=>   Nghiệm số:  x = x0 + bt, y = y0 – at  theo (6).

Trừ vế (3) với (13) và (4) với (14):

          a (x – x0) + b(y – y0) + c(z – z0)  =  0
         m(x – x0) + n(y – y0) + p(z – z0)  =  0

=>   Nghiệm số, theo (10) và (11):

=>   x = x0 + (bp – nc) t ,  y = y0 + (cm – pa) t , 
         z = z0 + (an – mb) t

Tóm lại, khi biết một nghiệm số đặc biệt của bài toán Diophantine, ta có thể biết được dạng tổng quát của các nghiệm số của nó. Nhưng làm sao tìm được một nghiệm số đặc biệt của bài toán? Thường thường là bằng cách dò dẫm từng bước một! Trong trường hợp đơn giản của phương trình (2), tác giả có tìm được cách sau đây, được phát biểu dưới dạng một định lý. Định lý nầy cần một định nghĩa về phép chia liên tiếp như sau:

Cho 2 số a và b. Giả sử a > b. Chia a cho b, ta có dư số r1; tiếp tục chia b cho r1, ta có dư số r2; chia r1 cho r2, ta có dư số r3, … cứ thế tiếp tục, lấy dư số của phép chia trước chia cho dư số của phép chia kế tiếp cho đến khi được dư số 0.

          a   = b q1    + r1          (15)
          b   = r1 q2  + r2          (16)
          r1 = r2 q3 + r3          
          r2 = r3 q4 + r4
          ……….
          rn = rn+1 qn+2 + 0

r1, r2, r3, … gọi là các dư số của phép chia liên tiếp a cho b. Các dư số nầy giảm dần đến 0.

Định lý:  Một nghiệm số của phương trình tuyến tính Diophantine
                                  
ax + by = c  với  a >  b
                    và  c ≠ 0, có thể tìm được khi c bằng một trong những dư số của
                    phép chia liên tiếp a cho b.

Để đơn giản, giả sử c =  r2, xem phương trình (16). Bằng cách đi ngược từ phương trình (16) trở lên phương trình (15) và thay các dư số bằng giá trị của chúng suy ra từ các phương trình đó , ta được:

           Từ (16), suy ra                    =>  c  =  r2 =  b – r1q2
           Thay r1 suy ra từ (15)     =>  c  =  b  – (a – bq1) q2

          Khai triển và rút gọn       =>  c  =  – aq2  +  b(1 + q1q2)
          Hay     a(– q2) +  b(1 + q1q2)  =  c

Suy ra, một nghiệm số của phương trình là  x =  – q2  và  y = 1 +  q1q2

 Thí dụ:    Xét phương trình Diophantine:

                        28x  +  15y  =  1                 (17)

Bằng cách chia liên tiếp 28 cho 15, ta được:

           28  =  15*1 + 13           (18)  
            15  =  13*1 +   2          (19)
            13  =    2*6 +   1          (20)
              2  =    1*2 +   0

Vế thứ hai của phương trình (17) bằng dư số 1 của phép chia liên tiếp 28 cho 15, nên phương trình (17) có 1 nghiệm số tìm được bằng cách đi ngược từ phương trình (20) trở lên phương trình (18):

          Từ (20), suy ra                    => 1 =  13 – 2*6
          Thay 2 suy ra từ (19)        => 1 =  13 – (15 – 13*1)*6  =  – 15*6 + 13*7
          Thay 13 suy ra từ (18)      => 1 =  – 15*6 + (28 – 15*1)*7   
          Khai triển và rút gọn         => 28*7 – 15*13 =  1

          Suy ra:   x = 7,  y = –13     là một nghiệm đặc biệt của phương trình (17).

          Theo trên, phương trình (17) có vô số nghiệm số có dạng:

                   x = 7 + 15 t  ,       y =  – (13 + 28 t)

Nếu không tìm được một nghiệm số đặc biệt nào của bài toán Diophantine thì sao? Trong trường hợp nầy, bài toán có thể giải bằng các điều kiện suy ra từ điều kiện Diophantine.

Phương pháp đó có thể tổng quát quá như trong hệ thống phương trình (3) & (4) với các hệ số cho sẵn như sau (để tránh phức tạp):

          27x + 9y + 22z   =   2578                 (21)
               x +    y  +     z   =       119                 (22)

với x, y và z là 3 số nguyên dương.

Trừ 1 ẩn số, thí dụ z, bằng cách nhân (22) với 22, rồi trừ vế:  

=>     5x – 13y  =  – 40             (23)
=>     x = (13y – 40) / 5           (24)

Hay    x = (2*5 + 3) y / 5 – 8  
            x =  2y – 8 + 3y / 5        (25)

Vì x, y là số nguyên, nên 3y/5 phải là bội số của 5 hay y phải là một bội số của  5

Đặt     y/5 =  t  với  t  là số nguyên dương hay 0   
=>     y = 5t              (26)

Thay y = 5t trong (25):
          x = 2*5t – 8 + 3t = 13t – 8                      (27)

Vì x > 0 => 13t – 8 > 0  => t > 8/13             (28)  

Thay trị số của x và y vào 22, suy ra:

          z = 119 – x – y = 119 – (13t – 8) – 5t
             =  127 – 18t                                               (29)

Vì z > 0 => 127 – 18t > 0 => t < 127/18              (30)

Theo 2 điều kiện (28) và (30), thì:  8/13 < t < 127/18  hay  0 < t < 8

Tóm lại, hệ thống phương trình (21) & (22) có 7 nghiệm số cho bởi các công thức:

          x = 13t – 8 y = 5t              z = 127 – 18t

 với  0 < t < 8  hay  t  có các trị số  1, 2, 3, 4, 5, 6  và  7.

Với  t = 1  => x =   5,  y =   5,  z = 109
Với  t = 7  => x = 83,  y = 35,  z =     1      

Sau cùng, mời độc giả hãy tự  giải bài toán sau đây:

Có bao nhiêu đồng tiền 50 xu (xu = 1/100 đồng), 20 xu và 10 xu biết rằng có tất cả có 51 đồng tiền với tổng số giá trị bằng 8 đồng 30 xu.

Thuận Hòa

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

 
%d bloggers like this: