Tài liệu Chuyên đề môn toán sử dụng nguyên tắc cực hạn để giải một số phương trình diophante

SỬ DỤNG NGUYÊN TẮC CỰC HẠN ĐỂ GIẢI MỘT SỐ PHƯƠNG TRÌNH DIOPHANTE I/ Mở đầu - Phương trình Diophante là phương trình có dạng: f(x1,x2,...,xn) = 0 Với f là đa thức n biến với hệ số nguyên Một bộ n-số ( x1o , x2o ,... xno )  0 với xio  ¢ i  1; n được gọi là 1 nghiệm nguyên của phương trình. - Thông qua việc giải phương trình Diophante, các nhà toán học đã tìm ra được những tính chất rất sâu sắc của số nguyên, số hữu tỉ... và sự ra đời của Liên phân số, thặng dư bình phương... Ngoài những liên hệ về lí thuyết với những vấn đề khác, còn có những ứng dụng trong kỹ thuật, chẳng hạn như phương trình Pell đã được ứng dụng rất nhiều trong thiên văn học. - Nói riêng, trong các kì thi học sinh giỏi quốc gia và quốc tế, phương trình Diophante thường xuất hiện dưới các hình thức khác nhau và được đánh giá là khó do tính không mẫu mực và lời giải độc đáo. - Nói chung không có một phương pháp nào đủ mạnh để giải quyết được tất cả các phương trình Diophante nhưng cũng có khá nhiều phương pháp hay, đẹp. Chẳng hạn như phương pháp gen cho phương trình Pell, bước nhảy Viet cho phương trình Marko, phương pháp lùi bậc vô hạn Fermat... II/ NGUYÊN TẮC CỰC HẠN * Một tập hợp hữu hạn khác rỗng bất kỳ của ¥ bao giờ cũng tồn tại phần tử lớn nhất và phần tử nhỏ nhất. * Đối với tập vô hạn, nguyên tắc này áp dụng cho tập con của tập số tự nhiên. - Thông thường trong việc giải các bài toán sơ cấp, nguyên lý này được sử dụng với phương pháp phản chứng. * Để chứng minh một phương trình là vô nghiệm nguyên, ta giả sử tập nghiệm nguyên của phương trình khác rỗng. Ta xây dựng một thứ tự trên nó và giả sử (x1,x2,...xn) là nghiệm nhỏ nhất (theo thứ tự đó). Ta phải tìm một cách nào đó để tìm ra 1 o o o một nghiệm ( x1 , x2 ,...xn )  ( x1 , x2 ,...xn ) (theo thứ tự) thì sẽ dẫn đến mâu thuẫn. Điều này chứng tỏ phương trình vô định. III/ Các ví dụ minh họa Ví dụ 1. Giải phương trình nghiệm nguyên: x3+3y3 = 9z3 (1) Lời giải: Dễ thấy nếu một trong ba số x, y, z bằng 0 thì hai số còn lại cũng bằng 0 nên (x,y,z) = (0,0,0) là một nghiệm nguyên của (1). Xét xyz  0, ta sẽ chứng minh (1) vô nghiệm nguyên. Giả sử (1) có nghiệm nguyên. Theo nguyên tắc cực hạn tồn tại nghiệm ( x0 , y0 , z0 )¢ của (1) thỏa mãn ( x0  y0  z0 ) nhỏ nhất. Có x03  3 y03  9 z 03 (2) Từ (2) vì 3 y03 ; 9 z03 3  x03 3  x0 3. Đặt x0 = 3x1; (1)  27 x13 +3 y03 =9 z03  9 x13 + y03 =3 z03 (3) 3  y 3 . Đặt y = 3y1: (2)  9 x13 + 27 y03 =3 z03 Từ (3)  y 3   3 x13 + 9 y03 = z03 (4) Từ (4)  z03 M3  z0 M3. Đặt z0 = 3z1: (3)  3x13  9 y13  27z13  x13  3 y13  9 z13 Do đó (x1, y1, z1) hay ( x1  y1  z1 = x0 y0 z0 , , 3 3 3 ) là một nghiệm của (1) nhưng rõ ràng x0 y z  0  0 < x0  y0  z0 (mâu thuẫn). 3 3 3 Vậy (x, y, z) = (0, 0, 0) là nghiệm nguyên duy nhất của (1). *NHẬN XÉT: Bằng phương pháp tương tự ta có thể chứng tỏ phương trình: x3 + py3 = p2z3 có nghiệm nguyên duy nhất (x, y, z) = (0, 0, 0) với p là số nguyên tố bất kì hay tổng quát hơn là phương trình: x1n  pxn2  p 2 x3n  ...  p n2 xnn  p n1 xnn1 có nghiệm nguyên duy nhất (x1,x2,...xn) = (0;0;.. Ví dụ 2. Giải phương trình nghiệm nguyên: x2 + y2 + z2 = 2xyz (1) (Korea 1996) Lời giải. 2 Dễ thấy nếu một trong ba số x,y,z bằng 0 thì hai số còn lại cũng bằng 0 nên (x,y,z)=(0,0,0) là một nghiệm nguyên của (1). Xét xyz  0, ta sẽ chứng minh (1) vô nghiệm nguyên. Theo nguyên tắc cực hạn tồn tại nghiệm ( x0 , y0 , z0 )¢ của (1) thỏa mãn x0 nhỏ nhất. Nếu trong ba số không có số nào chẵn thì VT  1 (mod 2), mà VP 2 (vô lý) Nếu trong ba số có ít nhất một số chẵn giả sử z0 2  x02  y02  0 (mod 4)  x0 , y0 đều chẵn. Do đó, cả ba số x0, y0, z0 đều chia hết cho 2. Đặt x0 = 2x1, y0 = 2y1, z0 = 2z1 (x1, y1, z1 ¢ ): (1)  x12  y12  z12  4x1 y1z1  x0 y 0 z 0  , ,  đều là nghiệm nguyên của (1) nhưng x0 < x0 (mâu thuẫn). 2 2 2 2  Vậy phương trình (1) có nghiệm nguyên duy nhất (x, y, z)=(0, 0, 0). Bài tập có cách làm tương tự: Ví dụ 3. Giải phương trình nghiệm nguyên 3x2 + 6y2 + 12z2 = t2 Ví dụ 4. Giải phương trình nghiệm nguyên x2 + 6y2 + 2z2 = 4t2 Ví dụ 5. Tìm tất cả bộ ba số nguyên (a, b, c) thỏa mãn a2 + b2 + c 2 = a2b2 (5th USA MO) Qua các VD, chắc các bạn đã nắm được khá rõ ý tưởng. Các bạn cũng dễ dàng giải được phương trình nghiệm nguyên a2 + b2 = 7c 2 hay chính là bài toán “ Chứng minh rằng 7 không thể phân tích được thành tổng các bình phương của 2 số hữu tỉ”. Câu hỏi đặt ra là với những số nguyên tố p nào ta có được bài toán tương tự? Ví dụ 6. Tìm tất cả các cặp số nguyên (x; y) thỏa mãn 2x – 1 = xy (1) (Putnam Mathematical Competition) Lời giải. Từ (1) dễ dàng suy ra x, y ≥ 0 Nếu x = 0  y = 0, Nếu y = 0  x = 0. 3 Nếu xy ≠ 0 : nhận thấy (x;y) = (1;1) là 1 nghiệm nguyên dương của (1). Ta sẽ chứng minh đây là nghiệm duy nhất. Giả sử (1) có nghiệm nguyên dương khác (1;1) Từ (1)  2x – 1 Mx. Gọi p là ước nguyên tố nhỏ nhất của x  2x – 1 Mp Đặt h = ord 2 p (h >1)  x Mh và 2h – 1 Mp , mà 2 p1  1 Mp (định lý Fermat nhỏ) h hay ƯC(x, p  1) >1  x có ít nhất một ước nguyên tố nhỏ hơn p (mâu  p  1M thuẫn). Vậy phương trình (1) có nghiệm nguyên (x;y) = (0;0); (1;1). Ví dụ 7. Tìm giá trị lớn nhất của biểu thức A = m2 + n2 với m, n là các số nguyên nằm trong khoảng từ 1 đến 1981 thỏa mãn: (n2 – mn - m2 )2 = 1 (1) (IMO 1981) Lời giải. Với m = n (1)  m4 = n4 = 1 <=> m = n = 1 Với m ≠ n: Nếu m > n thì 1 = | n2 – mn - m2 |= m2 + mn - n2 > mn > 1 (vô lý)  m < n Tương tự n < 2m Để ý rằng: n2 – mn - m2 = ( n2 – 2mn + m2 ) + mn - 2m2 = (n – m )2 + m (n – m) - m2 = - [m2 – m (n - m) - (n - m)2 ] Do đó, nếu (n; m) là 1 nghiệm nguyên của (1) thì (m, n-m) cũng là 1 nghiệm nguyên của (1). Ta xây dựng một dãy giảm trong đó tất cả các bộ số đều là nghiệm nguyên của (1): (*) (n,m) → (m, n-m) → (n-m, 2m-n) → ... (vì m b  (b; a-b) cũng là 1 nghiệm mà: b + (a-b) = a < a+b (vô lí)  a = b  (a;b) = (1;1)  dãy (*) kết thúc ở bộ (1;1) Tương tự, ta xây dựng một ánh xạ ngược bắt đầu từ (1;1) (1;1) → (2;1) → (3;2) → (5;3) →.....  Hai dãy là trùng nhau Để ý rằng: 1 = F 1 = F0 ; 2= F2 ; 3 = F3; 5 = F4... Do đó, nghiệm của (1) là tất cả các cặp số (F k+1; Fk) với Fk là số hạng thứ k của dãy Fibonacci nổi tiếng: F0 = F1 = 1 ; F n+1 = Fn + Fn-1. Vì 1 ≤ m,n ≤ 1981 và F 16 < 1981 < F17  m,n ≤ F16 nên maxA = F152  F162 = 1 346 269. Dấu “=” xảy ra  n = F16 = 987, m = F15 = 610. 4 Tiếp tục cuộc hành trình thú vị, ta sẽ đến với phương trình Fermat – phương trình đã điên đầu hàng trăm nhà toán học vĩ đại nhưng ta chỉ xét với trường hợp n = 4. Ví dụ 8. Chứng minh rằng phương trình sau không có nghiệm nguyên dương x4 + y4 = z4 Lời giải. Ta xét phương trình tương đương nhưng đơn giản hơn sau: x4 + y4 = z2 (1) Giả sử phương trình (1) có nghiệm nguyên dương. Không mất tính tổng quát, ta xét các nghiệm bộ 3 nguyên thuỷ (tức (x2, y2, z) = 1) do (1) là phương trình Pythagore) *Nếu x2; y2 p (p nguyên tố)  z2 p  z p  (x2, y2, z) > 1 (vô lý) Tương tự  x2, y2, z đôi 1 nguyên tố cùng nhau. Ta sẽ chứng minh: x, y khác tính chẵn lẻ. *Nếu x; y cùng tính chẵn lẻ  VP 4 (VÔ LÝ). Do đó x, y khác tính chẵn lẻ. Giả sử x chẵn, y lẻ. Theo nguyên tắc cực hạn tồn tại (x0,y0,z0) là nghiệm của (1) mà z0 nhỏ nhất. Vì (1) có dạng phương trình Pythagore nên  m, n  Z+, m > n, (m, n) = 1 sao cho x02  2mn ; y02  m2  n2 và z0  m2  n 2 Có y02  m2  n2  m2  y02  n2  m lẻ mà y02 = 2mn= m(2n) nên (m, 2n) = 1  m và 2n đều là số chính phương  n  2. Đặt m = m12 . Xét phương trình m2  y02  n2 dạng Pythagore nên  a, b  ¥ , a  b,(a, b)  1 sao cho: m  a 2  b 2 (*) y0  a 2  b2 n  2ab (do n 2) Có n = 2ab  2n = 4ab là số chính phương mà (a; b) = 1  a; b là 2 số chính 2 4 4 phương. Đặt a= a12 , b= b12 (*) có dạng: m1  a1  b1  (a1, b1, m1) là 1 nghiệm của (1) nhưng m1 < z0 (mâu thuẫn). Do đó, phương trình (1) vô nghiệm nguyên dương. Vậy có đpcm. Ví dụ 9. Chứng minh phương trình x4 – 4y4 = z2 không có nghiệm nguyên dương. Ví dụ 10. Tìm tất cả các cặp số nguyên không âm (x;y) thỏa mãn: x4 – 2y4 = 1 5 Gợi ý: Áp dụng VD8. Ví dụ 11. CMR Phương trình x4 – y4 = z2 không có nghiệm nguyên dương.   Ví dụ 12. Cho dãy số ( xn ) n1 và ( yn )n 1 được xác định như sau: x0 = 1, x1 = 4, xn+2 = 3xn+1 – xn với  n = 0; 1; 2;... y0 = 1, y1 = 2, yn+2 = 3yn+1 – yn với  n = 0; 1; 2;... 2 2 a) CMR: xn  5 yn  4  0 với  n = 0; 1; 2;... b) Giả sử a, b là các số nguyên dương mà a2 – 5b2 + 4 = 0. Chứng minh tồn tại số tự nhiên k sao cho xk = a và xk = b. (VMO 1999) Lời giải: a) Ta dễ dàng chứng minh được công thức sau theo quy nạp: 3 5 1 3 xn1  xn  yn ; yn 1  xn  yn 2 2 2 2 2 2 Từ đó, ta lại chứng minh công thức: xn  5 yn  4  0 theo quy nạp (1) Với n = 0: 1 – 5 + 4 = 0  (1) đúng. Giả sử (1) đúng với n = k. Ta chứng minh (1) đúng với n = k+1 2 2 k 1 Có x  5y 2 k 1 2 5  3  3 1  4   xk  yk   5  xk  yk   4 2  2  2 2  xk2  5 yk2  4  0 đúng. Do đó, (1) đúng (đpcm). b) x2 – 5y2 + 4 = 0 (1) Gọi ( a0 ; b0 ) là 1 nghiệm nguyên dương bất kì (1) 2 2 Thay vào (1) có a0  5b0  4  0 . Dựa vào phần a), ta đặt 3 5 a1  b1 2 2 1 3 b0  a1  b1 2 2 a0  3a0  5b0 2 3b  a b1  0 0 2 a1   Bây giờ ta tìm điều kiện để a1; b1 là các số nguyên dương, vì a 02  5b 02 +4=0  a 02  b 02 (mod 4)  a 0 và b 0 khác tính chẵn lẻ nên a 1 ,b 1  Z . Vì a 02 =5b 02  4< 9b 02  a 0 < 3b 0  b 1 >0. 6 3 5 9 5 Để a 1 > 0  3a 0 > 5b 0  a 02 = 5b 02  4  5( a 0 ) 2 - 4= a 02 - 4  a 02  5  a 0  3. Do đó, nếu ta xét a 0  3 thì sẽ có điều kiện sau: (a 0 ,b 0 ) là một nghiệm nguyên dương của (1) thì ( 3a0  5b0 3b0  a0 , 2 2 ) cũng là một nghiệm nguyên dương của (1). Từ đó ta xây dựng một dãy giảm trong đó tất cả các bộ số đều là nghiệm nguyên dương của (1). (*) 3 2 (a 0 ,b 0 )  ( a 0  5 b0)  2 ... Theo nguyên tắc cực hạn tồn tại (m,n) là một bộ của dãy thỏa mãn (m+n) nhỏ nhất.  (m 1 ,n 1 ) cũng là một bộ của dãy với m1 = 3m  5n , 2 n1 = 3n  m 2 Nhưng m 1 + n 1 = m  n < m+n (vô lí). Vì vậy a 0 hay m < 3  m=1;2. Nếu m =2  5n 2 =8 (Vô lí) Nếu m =1  5n 2 =5  n=1 Do đó, dãy (*) kết thúc bằng bộ (1,1) mà theo phần a) ta đã xây dựng được một ánh xạ ngược: (**) (1,1)  (4,2)  ...  dãy (*) và (**) trùng nhau. Vậy có đpcm *NHẬN XÉT: 3 5 1 3 Để tìm ra công thức: xn1  xn  yn ; yn 1  xn  yn ta có thể làm như sau: 2 2 2 2 Đặt x n1 = ax n + by n .Thay n=0 và n=1 ta có hệ phương trình: 4 = a+b và 11= 4a+2b ta được a= 3 2 , b= 5 . 2 3 5 x n + y n .Từ đây ta chứng minh bằng quy nạp 2 2 1 3 Tương tự ta tìm ra y n1 = x n + y n . 2 2  x n1 = Bây giờ chúng ta sẽ cùng xem xét một số phương trình Diophante bậc hai trong đó có mặt một tham số chưa biết và ta cần tìm tất cả các giá trị của tham số để phương trình có nghiệm nguyên. Ví dụ 13. Tìm tất cả các số nguyên dương n để phương trình: x 2 +y 2 +1= nxy (1) có nghiệm nguyên dương. Lời giải: Vì x 2 +y 2 +1  2xy+1  n>2  n  3 Với n=3: (1) có dạng x 2 +y 2 +1= 3xy và có nghiệm nguyên dương (x,y)=(1,1) Với n>3 : Giả sử phương trình (1) có nguyên dương. Theo nguyên tắc cực hạn tồn tại (a,b) là một nghiệm nguyên dương của (1) thỏa mãn a>b và (a+b) nhỏ nhất.  a là một nghiệm của phương trình: x 2  nb.x +b 2 +1=0 (*) Gọi c là nghiệm còn lại của (*). Theo Viet có: a+c = nb  c = nb  a > 0 7 Do đó (nb-a, b) cũng là nghiệm nguyên dương của (1) Nếu nb  a  a  nb  2a, thay vào a 2 +b 2 +1= nab có: 2 2 2 2 2 a +b +1  2a  a  b +1(mâu thuẫn)  nb  a < a  (nb  a)+b < a+b (mâu thuẫn) Vậy với duy nhất n=3 phương trình (1) có nghiệm nguyên dương. Tổng quát hơn ta có Markov’equation như sau: Ví dụ 14. Tìm tất cả các số nguyên dương n để phương trình : x 2 +y 2 +z 2 = nxyz có nghiệm nguyên dương (1) Lời giải: Với n=1: (1) có nghiệm (3,3,3) Với n=2: theo VD 2 , (1) không có nghiệm nguyên dương Với n=3: (1) có nghiệm (1,1,1) Ta sẽ chứng minh (1) vô nghiệm nguyên dương với mọi n > 3. Giả sử khi đó (1) có nghiệm nguyên dương.Theo nguyên tắc cực hạn tồn tại (a,b,c) là một nghiệm nguyên dương của (1) thỏa mãn a  b  c và (a+b+c) nhỏ nhất. (*)  a một là nghiệm của phương trình: x 2  nbc.x+b 2 +c 2 =0 Trường hợp1: a>b, gọi d là nghiệm còn lại của phương trình (*). Theo Viet: a+d = nbc ad = b 2 +c 2  d = nbc  a > 0  (d,b,c) cũng là một nghiệm nguyên dương của (1)  d  a  b 2 +c 2  nbc+1=(a  1)(d  1)  b 2  c(nb  c)  1 Do nb  c  nc  c  1 , c  1 nên c=1  Phương trình a 2 +b 2 +1= nab có nghiệm nguyên dương với n  3 (mâu thuẫn VD 13) Trường hợp 2: a=b.Thay vào có 2a 2 + c 2 = na 2 c  c 2 = a 2 (nc-2)  c 2 (nc-2)  nc  3  n  3 (Vô lí) Vậy với duy nhất n=3 phương trình (1) có nghiệm nguyên dương. Ví dụ 15. Xét các số tự nhiên lẻ a, b mà a là ước số của b 2 + 2 và b là ước số của a 2 +2. Chứng minh rằng a và b là các số hạng của dãy số tự nhiên ( vn ) xác định bởi: vn = 4 vn 1 – vn 2 với mọi n ≥ 2. (VMO 2012) Lời giải: Nếu a và b cùng chia hết cho số nguyên tố p nào đó thì vì a 2 +2Mb nên 2Mp  p=2  a chẵn (mâu thuẫn). Do đó (a,b) = 1. Từ a 2 +2Mb  a 2 + b 2 +2Mb, b 2 + 2Ma  a 2 + b 2 +2Ma Nên a 2 + b 2 +2Mab  phương trình a 2 + b 2 +2 = nab (1) với n N có nghiệm tự nhiên. Nếu một trong hai số bằng 0, giả sử a=0 thì b 2 +2=0 (vô lí)  a,b > 0. Vì a 2 + b 2 +2  2ab+1  n>2  n  3. Ta sẽ chứng minh với n>3 phương trình (1) vô nghiệm nguyên dương. Theo nguyên tắc cực hạn tồn tại (x,y) là một nghiệm nguyên dương của (1) thỏa mãn x>y và (x+y) nhỏ nhất.  x là một nghiệm của phương trình: a 2  nya +y 2 +2=0 (*) 8 Gọi z là nghiệm còn lại của (*). Theo Viet có: x+z = ny  z = ny  x > 0 Do đó (nb-a, b) cũng là nghiệm nguyên dương của (1) Nếu ny  x  x  ny  2x, thay vào x 2 +y 2 +2= nxy có: x 2 +y 2 +2  2x 2  x 2  y 2 +2 (mâu thuẫn)  ny  x < x  (ny  x)+y < x+y (mâu thuẫn) Vậy phương trình (1) có nghiệm chỉ với n=3. Xét phương trình a 2 + b 2 +2 = 3ab (2) Ta cần chứng minh a và b là các số hạng của dãy số tự nhiên ( vn ) xác định bởi: vn = 4 vn 1 – vn 2 với mọi n ≥ 2 hay ta chứng minh các nghiệm nguyên dương của (2) đều thuộc dãy ( vn ) . Để có điều này ta chỉ cần làm tương tự như câu b)VD 12. Ví dụ 16. Tìm tất cả các cặp số nguyên dương (a,b) thỏa mãn a 2 +b 2 +1 chia hết cho ab+a+b. Ví dụ 17. Giải hệ phương trình nghiệm nguyên dương: x 2 +1=uy y 2 +1=vx Ví dụ 18. Chứng minh rằng không tồn tại 2 số nguyên mà tổng, hiệu bình phương của chúng là số chính phương. Ví dụ 19. Tìm tất cả các cặp số nguyên không âm (m,n) thỏa mãn: (m+n  5) 2 = 9mn (USA TST 2001) Ví dụ 20. Giải phương trình nghiệm nguyên dương của phương trình: x 2  y 2  x  y  1  xyz Ví dụ 21. Nếu phương trình x 2 +y 2 +1= nxy có nghiệm nguyên dương , hãy tìm tất cả các nghiệm của nó. Ví dụ 22. Cho x, y, z là các số nguyên dương thỏa mãn xy  z 2  1 . Chứng minh tồn tại các số nguyên khong âm a, b, c, d thỏa mãn: x  a 2  b 2 , y  c 2  d 2 , z  ac  bd . (IMO shortlist 1979) Ví dụ 23. Nếu a, b, c là các số nguyên dương sao cho 0 < a 2  b 2  abc ≤ c Chứng minh rằng a 2  b 2  abc là số chính phương. (CRUX, Problem 1420) Tài liệu tham khảo 1. Titu Andreescu. An introduction to Diophante Equations, 2014 2. Hà Huy Khóai - Phạm Huy Điển. Số học thuật toán, NXB ĐHQG HN 2003. 3. Lê Hải Châu. Các bài thi học sinh giỏi Toán PTTH toàn quốc, NXBGD 1994. 4. Nguyễn Sinh Nguyên, Nguyễn Văn Nho, Lê Hoành Phò. Tuyển tập các bài dự tuyển Olympic Toán học Quốc tế 1991-2001, NXBGD 2003. 5. Nguyễn Văn Nho. Olympic Toán học châu Á – Thái Bình Dương 1989-2002, NXBGD 2003. 6. Tập thể tác giả. Tuyển tập 5 năm Tạp chí Toán học và Tuổi trẻ, NXBGD 2003. 7. Arthur Engel. Problem Solving Strategies, Springer 1998 8. Goeoge Polya. Gabor Szego. Problems and Theorems in Analysis II, Springer 1976 9. Harvey Cohn. Advanced Number Theory, Dover Publications 1980 9