Luận văn Một số lớp phương trình diophantine

thoả mãn điều kiện 5a ≥ 7b. Chứng minh rằng hệ x+2y+3z+7u= a,y+2z+5u= b luôn có nghiệm nguyên không âm. 21 Chứng minh. Giả sử b = 5u+ v với 0 ≤ u, 0 ≤ v ≤ 4. Từ điều kiện a ≥ 7b5 suy ra a≥ 7(5u+v)5 . Từ đây ta có a−7u≥ 7v 5 . (1.10) Như vậy hệ phương trình có thể viết là{ x+2y+3z= a− yu y+2z= b−5u= v. (1.11) Với mỗi 0≤ v≤ 4 ta sẽ chọn y, z thích hợp để có x= z−7u−2y−3z≥ 0. • Nếu v= 0, ta lấy y= z= 0. Khi đó x= a−7u≥ 7v5 = 0 (theo (1.10))). • Nếu v= 1, ta thấy y= 1, z= 0. Khi đó x= a− yu−2≥ 7v 5 −2= 7 5 −2>−1. Vậy x≥ 0. • Nếu v= 2, ta lấy y= 0, z= 1. Khi đó x= a−7u−3≥ 7v 5 −3= 14 5 −3>−1. Vậy x≥ 0. • Nếu v= 3, ta lấy y= z= 1. Khi đó x= a−7u−5≥ 7v 5 −5= 21 5 −5>−1. Vậy x≥ 0. • Nếu v= 4, ta lấy y= 0, z= 2. Khi đó x= a−7u−6≥ 7v 5 −6= 28 5 −6>−1. Vậy x≥ 0. Tóm lại với mọi v= 0, 1, 2, 3, 4 ta đều chọn được y, z, x không âm để (1.11) được nghiệm đúng. Bài toán được giải xong. 22 Bài toán 1.2.6 (Đề thi vô địch Mỹ 1982). Chứng minh rằng tồn tại số tự nhiên k sao cho tất cả các số kn+1 với n= 1,2, . . . đều là hợp số. Lời giải. Xét các số Fermat Fm = 22 m +1. Ta đã biết Fm là số nguyên tố với m = 0,1,2,3,4, trong khi Euler phát hiệu rằng F5 là một hợp số, F5 là tích của hai số nguyên tố 641 và 6700417. Ký hiệu ai = Fi với i= 0,1,2,3,4, a5 = 641a6 = 6700417. Theo Định lí Trung Hoa về thặng dư, tồn tại số tự nhiên k > max(a0, . . . ,a6) để k ≡ 1 (mod am) với m= 0,1,2, . . . ,5 và k ≡−1 (mod a6). Ta sẽ chứng minh k chính là số cần tìm. Xét n bất kỳ, n có thể viết dưới dạng n= 2mp với 0≤ m và p lẻ. (a) Nếu m≤ 4, ta có k ·2n+1≡ 2n+1 (mod am). Mặt khác 2n+1= 22 m p+1= (22 m )p+1 ... 22 m +1= am. Do đó k ·2n+1 ... am. Vì k ·2n+1> k > am nên k ·2n+1 là hợp số. (b) Nếu m= 5 thì k ·2n+1≡ 2n+1 (mod a5). Mặt khác 2n+1= ( 22 5 )p +1 ... 22 5 +1= F5 ... 641= a5. Vậy k ·2n+1 ... a5. Mặt khác k ·2n+1> a5, suy ra k ·2n+1 là hợp số. (c) Nếu m≥ 6, khi đó n= 26b với b ∈ Z. Ta có k ·2n+1≡−2n+1 (mod a6), 2n = ( 22 5 )2b = (F5−1)2b ≡ (−1)2b ≡ 1 (mod a6) vì F5 ... a6. Do đó k ·2n+1≡−1+1= 0 (mod a6). Vì k ·2n+1> a6 nên k ·2n+1 là hợp số. Vậy với mọi n, số k ·2n+1 luôn là hợp số. 23 Chương 2 Một số phương trình Diophantine phi tuyến 2.1 Phương trình Pell loại 1 Phương trình Pell loại 1 là phương trình có dạng x2−Dy2 = 1, (2.1) trong đó D ∈ N∗ và ta yêu cầu tìm nghiệm x,y ∈ N∗ . Trong tiết này khi nói đến nghiệm của (2.1) ta hiểu là nghiệm nguyên dương. Định lí 2.1.1 (Điều kiện tồn tại nghiệm). Phương trình (2.1) có nghiệm nguyên dương khi và chỉ khi D là số không chính phương. Chứng minh. Giả sử D= m2. Khi đó x2−Dy2 = x2−m2y2 = 1→ (x−my)(x+my) = 1 → x−my= x+my= 1→ x= 1,y= 0. Vậy (2.1) không có nghiệm nguyên dương. Ngược lại giả sử D là số không chính phương. Ta có các bổ đề sau Bổ đề 2.1.2. Cho α /∈Q. Khi đó tồn tại vô số cặp nguyên (h,k) với k > 0 sao cho∣∣∣∣α− hk ∣∣∣∣< 1k2 . 24 Chứng minh. Ta sử dụng nhận xét đã biết sau: Với mỗi q ∈ N∗ tồn tại cặp số nguyên (h,k) với 1≤ k ≤ q sao cho∣∣∣∣α− hk ∣∣∣∣< 1kq . Ký hiệu A= { (h,k) : ∣∣∣∣α− hk ∣∣∣∣< 1k2 } . Ta phải chứng minh |A| = ∞. Giả sử trái lại |A| < ∞. Khi đó tồn tại ε sao cho∣∣∣∣α− hk ∣∣∣∣> ε với mọi (h,k) ∈ A. Chọn q ∈ N∗ sao cho 1 q < ε. (2.2) Theo nhận xét trên tồn tại cặp số nguyên (h0,k0) với 1≤ q sao cho∣∣∣∣α− h0k0 ∣∣∣∣< 1k0q ≤ 1k20 . (2.3) Từ (2.3) ta có (h0,k0) ∈ A→ ∣∣∣∣α− h0k0 ∣∣∣∣> ε . Nhưng 1q ≥ 1k0q > ∣∣∣∣α− h0k0 ∣∣∣∣> ε . Mâu thuẫn với (2.2). Bổ đề 2.1.3. Tồn tại vô số cặp số nguyên dương (x,y) sao cho |x2−Dy2|< 1+2 √ D. Chứng minh. Theo Bổ đề 2.1.2 tồn tại vô số cặp số nguyên (x,y) sao cho 0< ∣∣∣∣√D− xy ∣∣∣∣< 1y2 . Suy ra ∣∣∣∣xy+√D ∣∣∣∣= ∣∣∣∣xy−√D+2√D ∣∣∣∣< 1y2 +2√D. Vậy |x2−Dy2|=|x− y √ D||x+ y √ D|= y2 ∣∣∣∣xy−√D ∣∣∣∣ ∣∣∣∣xy+√D ∣∣∣∣ < y2 1 y2 ( 1 y2 +2 √ D) = 1 y2 +2 √ D< 1+2 √ D. 25 Chứng minh định lý Từ bổ đề 2.1.3 (x,y) tồn tại vô số cặp số nguyên dương (x,y) sao cho |x2−Dy2|< 1+2 √ D. Đặt I = [−1−2√d;1+2√d]. Với mỗi k ∈ I ký hiệu Ak = {(x,y) ∈ N∗ : x2−Dy2 = k} Do đó tồn tại k ∈ I để |Ak|= ∞. Suy ra tồn tại (x1,y1) 6= (x1,y1) ∈ Ak để x1 ≡ x2 (mod |k|) y1 ≡ y2 (mod |k|), x21−Dy21 = x22−Dy22 = k, Xét tích (x1− y1 √ D)(x2+ y2 √ D)x1x2−Dy1y2+ √ D(x1y2− x2y1) (2.4) Vì x1x2−Dy1y2 ≡ x21−Dy21 ≡ 0 (mod |k|) x1y2− x2y1 ≡ x1y1− x1y1 ≡ 0 (mod |k|). Vậy tồn tại u,v ∈ Z sao cho x1x2−Dy1y2 = ku (2.5) x1y2−Dy1x2 = kv (2.6) Từ (2.4), (2.5), (2.6) suy ra (x1− y1 √ D)(x2+ y2) = k(u+ v √ D), (x1+ y1)(x2− y2 √ D) = k(u− v √ D). Nhân hai đẳng thức trên với nhau và chú ý rằng (x1,y1,(x2,y2) ∈ Ak→ x21−dy21 = x22−dy22 = k ta được k2 = k2(u2−Dv2)→ u2−Dv2 = 1. 26 Ta chứng minh u,v > 0. Rõ ràng u > 0. Nếu trái lại v = 0 thì u = ±1→ (x1− y1 √ D)(x2+ y2 √ D) = ±k = ±(x21−Dy21) = ±(x1− y1 √ D)(x1+ y1 √ D)→ x2+ y2 √ D = x1+ y1 √ D→ x1 = x2,y1 = y2. Ta có mâu thuẫn. Vậy (u,v) là nghiệm nguyên dương của phương trình (2.1). Định lí 2.1.4 (Công thức nghiệm). Ký hiệu (a,b) là nghiệm nhỏ nhất của phương trình x2−Dy2 = 1. Khi đó dãy (xn,yn) cho bởi xn = (a+b √ D)n+(a−b√D)n 2 , yn = (a+b √ D)n− (a−b√D)n 2 √ D . cho tất cả các nghiệm của (2.2) Dãy nghiệm (xn,yn) cũng có thể xác định theo công thức truy hồi sau x0 = 1,x1 = a,xn+2 = 2axn+1− xn, (2.7) y0 = 0,y1 = b,yn+2 = 2ayn+1− yn. (2.8) Chứng minh. Ta có xn+ yn √ D= (a+b √ d)n,xn− yn = (a−b √ d)n. (2.9) Suy ra (x2n−Dy2n) = (a2−Db2)n = 1. Đảo lại giả sử (x,y) là nghiệm bất kỳ của (2.1). Ta chứng minh tồn tại n ∈ N∗ để x = xn;y = yn. Vì D không chính phương nên điều này tương đương Tồn tại n ∈ N∗ để x+ y √ D= xn+ yn √ D= (a+b √ D)n. Chứng minh bằng phản ứng. Giả sử trái lại x+ y √ D 6= (a+b √ D)n∀n ∈ N∗. 27 Khi đó tồn tại m ∈ N∗ sao cho (a+b √ D)m < x+ y √ D< (a+b √ D)m+1. Nhân hai vế với (a−b√D)m ta được 1< (x+ y √ D)(a−b √ D)m < a+b √ D. Do (2.9) ta có (x+ y √ D)(a−b √ D)m = (x+ y √ D)(xm− ym √ D) = (xxm−Dyym)+(xmy− ymx) √ D = u+ v √ D, ở đó u= xxm−Dyym,v= xmy− ymx. Vậy 1< u+ v √ d < a+b √ d. (2.10) Ta có u2−Dv2 = (xxm−Dyym)2−D(xmy− ymx)2, = (x2−Dy2)(x2m−Dy2m) = 1. Lại có x > y √ d,xm > ym √ d nên u > 0. Lại có (u− v√D)(u+ v√D) = 1 và 1 < u+v √ d nên 0 0. Vậy (u,v) là nghiệm của (2.1) do đó a ≤ u,b ≤ u→ a+ b√d ≤ u+ v√d trái với (2.10). Định lý được chứng minh. Từ định lý trên ta thấy việc tìm nghiệm của phương trình Pell (2.1) quy về tìm nghiệm nhỏ nhất (a,b) của nó. Cách đơn giản nhất là thử bằng tay: Thay lần lượt y= 1,2, . . . vào biểu thức 1+Dy2 cho tới khi nào được số chính phương thì dừng lại. Vì phương trình (2.1) có nghiệm nên chắc chắn quá trình này sẽ dừng lại sau b phép thử. Khi đó nghiệm nhỏ nhất là (a,b) với a= √ 1+Db2 . Nếu nghiệm nhỏ 28 nhất b này lớn thì cách thử này không khả thi. Thí dụ với phương trình x2− 61y2 thì cặp nghiệm nhỏ nhất là a= 1766319049, b= 226153980. Sau đây ta sẽ trình bày một thuật toán sử dụng liên phân số để tìm một nghiệm nhỏ nhất (a,b) của (2.1). Định nghĩa 2.1.5. Cho a0,a1,a2, . . . là dãy số nguyên trong đó ai > 0, i≥ 1. Đặt Ck = [a0;a1, . . . ,ak]. Khi đó tồn tại giới hạn limCk = α. Ta gọi α là giá trị của liên phân số vô hạn [a0,a1,a2, . . .]và viết α = [a0,a1,a2, . . .]. Định lí 2.1.6. α = [a1,a1,a2, . . .] là một số vô tỷ. Ngược lại mỗi số vô tỷ đều biểu diễn duy nhất dưới dạng một liên phân số vô hạn. Định nghĩa 2.1.7. Ta gọi liên phân số vô hạn α = [a1;a1,a2, . . .] là tuần hoàn nếu dãy (an) tuần hoàn kể từ một chỉ số nào đó tức là: Tồn tại các số nguyên dương m và k sao cho mọi n ≥ m ta có an = am+k. Số nguyên dương k được gọi là chu kỳ của liên phân số α = [a0;a1,a2, . . .]. Khi đó ta viết α = [a0;a1,a2, . . . ,am−1,am,am+1, . . . ,am+k−1]. Nếu D là số không chính phương, biểu diễn liên phân số của √ D được cho bởi Định lí 2.1.8. Biểu diễn liên phân số của √ D là tuần hoàn và có dạng √ D= [a;a1,a2, . . . ,an,2a]. với a= [ √ D]. Hơn nữa có công thức tường minh để xác định dãy (a1, . . . ,an). Chú ý rằng dãy (a1, . . . ,an) là đối xứng tức là a1 = an,a2 = an−1, . . . 29 Ví dụ 2.1.9. √ 23= [4;1,3,1,8] √ 29= [5;2,1,1,2,10] √ 31= [5;1,1,3,5,3,1,1,10] √ 46= [6;1,2,1,1,2,6,2,1,1,2,1,12] √ 76= [8;1,2,1,1,5,4,5,1,1,2,1,16] √ 97= [9;1,5,1,1,1,1,1,1,5,1,18]. Định lí 2.1.10. Cho phương trình Pell x2−Dy2 = 1. (I) 1. Biểu diễn √ D thành liên phân số √ D= [a;a1,a2, . . . ,an,2a]. 2. Nếu chu kỳ n là số chẵn ta tính giản phân thứ n−1 Cn−1 = pn−1 qn−1 . 3. Khi đó (pn−1,qn−1) là nghiệm nhỏ nhất của (2.1) 4. Nếu chu kỳ n là số lẻ ta tính giản phân thứ 2n−1 C2n−1 = p2n−1 q2n−1 . 5. Khi đó (p2n−1,q2n−1) là nghiệm nhỏ nhất của (2.1) Ví dụ 2.1.11. Tìm nghiệm nhỏ nhất của phương trình x2−14y2 = 1. Ta có√14= [3;1,2,1,6]. Chu kỳ n= 4 là số chẵn. Vậy ta tính giản phân C3 = [3,1,2,1] = 3+ 1 1+ 1 2+ 1 1 30 = 15 4 . Vậy nghiệm nhỏ nhất là (15,4). Ví dụ 2.1.12. Tìm nghiệm nhỏ nhất của phương trình x2−13y2 = 1. Ta có√13= [3;1,1,1,1,6] = [3,1,1,1,1,6,1,1,1,1,6, . . . Chu kỳ n= 5 là số lẻ. Vậy ta tính giải phân C9 = [3,1,1,1,1,6,1,1,1] = 3+ 1 1+ 1 1+ . . .+ 1 1+ 1 1 = 649 180 . Vậy nghiệm nhỏ nhất là (649,180) Trở lại phương trình x2−61y2 = 1. Ta có √ 76= [7;1,4,3,1,2,2,1,3,4,1,14] Chu kỳ n= 11 là số lẻ. Ta tính giản phân C21 = [7,1,4,3,1,2,2,1,3,4,1,14,1,4,3,1,2,2,1,3,4,1] = 7+ 1 1+ 1 4+ 1 3+ . . .+ 1 4+ 1 1 = 1766319049 226153980 Vậy nghiệm nhỏ nhất là (1766319049,226153980) 2.2 Phương trình Pell loại 2 Phương trình Pell loại 2 là phương trình x2−Dy2 =−1 (2.11) ở đó D ∈ N∗ . Nghiệm của (2.11) luôn được hiểu là nghiệm nguyên dương. 31 Định lí 2.2.1. Điều kiện cần để (2.11) có nghiệm là D không là số chính phương và D không có ước nguyên tố dạng 4k+3. Chứng minh. i) nếu D=m2 thì (2.11) trở thành (my−x)(my+x) = 1→my− x= my+ x= 1→ x= 0 vậy (2.11) vô nghiệm. ii) NếuD có ước nguyên tố p= 4k+3 : Giả sử (x,y) là nghiệm. Khi đó x2+1= Dy2→ p|x2+1. Vì p= 4k+3 nên p|1. Mâu thuẫn. Tuy nhiên, đây không là điều kiện đủ. Định lí 2.2.2. Nếu D= p là số nguyên tố thì (2.11) có nghiệm khi và chỉ khi p= 2 hoặc p 6= 4k+3. Chứng minh. Nếu (2.11) có nghiệm thì từ Định lý 1 suy ra p= 2 hoặc p 6= 4k+3. Đảo lại nếu p= 2 thì phương trình x2 =−2y2 =−1 có nghiệm (x,y) = (1;1). Xét p≡ 1( mod 4). Xét phương trình Pell loại I x2−Dy2 = 1 (2.12) Gọi (a,b) là nghiệm nhỏ nhất của (2.12). Ta có a2−1= pb2. Nếu a chẵn thì b lẻ do đó b2 ≡ 1( mod 4)→ a2 ≡ 1+ p≡ 2( mod 4). Mâu thuẫn. Vậy a lẻ, b chẵn. Đặt a = 2a1+ 1,b = 2b1. Ta có (a− 1)(a+ 1) = pb2⇔ a1(a1+ 1) = pb21. Do p nguyên tố và (a1,a1+1) = 1 nên a1= u2,a1+1= pv2 hoặc a1= pu2,a1+1= v2. Nếu a1 = u2,a1+ 1 = pv2 → u2− pv2 = −1. Vậy (2.11) có nghiệm (u,v). Nếu a1 = pu2,a1+ 1 = v2 → v2− pu2 = 1. Vậy (v,u) là nghiệm của (2.12). Suy ra u≥ a→ a1+1= v2 ≥ v≥ a= 2a1+1. Mâu thuẫn. Định lí 2.2.3. Gọi (a,b) là nghiệm nhỏ nhất của (2.12). Khi đó (2.11) có nghiệm khi và chỉ khi  a= x 2+Dy2 b= 2xy (2.13) 32 có nghiệm nguyên dương. Hơn nữa nếu (2.13) hệ có nghiệm nó sẽ có nghiệm duy nhất. Nghiệm duy nhất (x1,y1) này chính là nghiệm nhỏ nhất của (2.11). Chứng minh. 1) Giả sử (2.11) có nghiệm. Gọi (x1,y1) là nghiệm nhỏ nhất của (2.11). Đặt u= x21+Dy 2 1,v= 2x1,y1. Ta chứng minh u= a,v= b do đó (x1,y1) chính là nghiệm của (2.13). Ta có u2−Dv2 = (x21−Dy21)2 = 1. Vậy (u,v) là nghiệm của (2.12). Suy ra u≥ a;v≥ b. Ta có (a2−Db2)(x1−Dy21) = 1(−1) =−1 ⇔(ax1−Dby1)2−D(ay1−bx1)2 =−1. Dễ thấy (ax1−Dby1)2 > 0,(ay1− bx1)2 > 0. Do (x1,y1) là nghiệm của (2.11) nên (ax1−Dby1)2 ≥ x21⇔ a2x21+D2b2y21− x21 ≥ 2abDx1y1 → x21(a2−1)+D2b2y21 ≥ 2abDx1y1 → x21Db2+D2b2y21 ≥ 2abDx1y1 → b(x21+dy21)≥ 2ax1y1→ bu≥ av → b2u2 ≥ a2v2→ b2(Dv2+1)≥ v2(Db2+1) → b≥ v→ b= v→ u= a. 2) Đảo lại giả sử (u,v) là nghiệm của (2.13). Ta có a2−Db2= 1⇔ (u2+Dv2)2− D(2uv)2 = (u2−Dv2)2 = 1. Vậy u2−Dv2 = 1 hoặc u2−Dv2 = −1. Nếu u2−Dv2 = 1 thì (u,v) là nghiệm của (2.12) do đó u ≥ a = u2+Dv2. Mâu thuẫn. Vậy u2−Dv2 =−1 do đó (2.11) có nghiệm (u,v). Tiếp theo ta chứng minh (u,v) là nghiệm nhỏ nhất của (2.11). Giả sử (x1,y1) là nghiệm nhỏ nhất của (2.11). Theo chứng minh ở 1) ta có a= u2+Dv2 = x21+ Dy21;b= 2uv= 2x1y1→ u2+Dv2+2uv= x21+Dy21+2x1y1→ (u+v √ D)2 = (x1+ y1)2→ u= x1;v= y1. Định lý được chứng minh. 33 Ví dụ là một áp dụng của định lý 2. Nó cũng chỉ ra rằng điều kiện của định lý 1 chỉ là điều kiện cần. Ví dụ 2.2.4. Chứng minh rằng phương trình x2− 34y2 = −1 vô nghiệm (Ở đây 34= 2.17 không số chính phương và cũng không có ước nguyên tố dạng 4k+3). Giải Phương trình x2−34y2 = 1 có nghiệm nhỏ nhất là (a;b) = (35;6). Xét hệ35= x 2+34y2 6= 2xy Từ phương trình thứ nhất của hệ suy ra (x;y) = (1;1). Tuy nhiên (1;1) không thoả mãn phương trình thứ hai. Vậy hệ vô nghiệm do đó theo định lý 2 phương trình x2−34y2 =−1 vô nghiệm. Ta thừa nhận định lý Định lí 2.2.5. Phương trình Pell loại 2 x2−Dy2 =−1 có nghiệm khi và chỉ khi trong biểu diễn √ D thành liên phân số √ D= [a;a1,a2, . . . ,an,2a] chu kỳ n là số lẻ. Trong trường hợp đó (pn−1,qn−1) là nghiệm nhỏ nhất của phương trình ở đó. Cn−1 = pn−1 qn−1 là giải phân thứ n−1. Ví dụ 2.2.6. i) Xét phương trình x2−13y2 = −1. Ta có √D = [3;1,1,1,1,6]. Chu kỳ n= 5 là số lẻ. Vậy phương trình có nghiệm. Ta tính giản phân C4 = [3,1,1,1,1] 34 = 3+ 1 1+ 1 1+ 1 1+ 1 1 = 3+ 3 5 = 18 5 Vậy nghiệm nhỏ nhất là (18,5) ii) Xét phương trình x2−34y2 =−1. Ta có√34= [5;1,4,1,10]. Chu kỳ n= 4 là số chẵn. Vậy phương trình vô nghiệm. Định lí 2.2.7 (Công thức nghiệm). Giả sử phương trình Pell loại 2 x2−Dy2 =−1 (II) có nghiệm. Gọi (α,β ) là nghiệm nhỏ nhất của nó. Khi đó dãy (xn,yn)∞n=1 cho bởi xn = (α+β √ D)2n−1+(α−β√D)2n−1 2 yn = (α+β √ D)2n−1+(α−β√D)2n−1 2 √ D cho ta tất cả các nghiệm của (II). Chứng minh. Giả sử (xn,yn) cho bởi công thức trên. Khi đó xn+ yn √ D= (α+β √ D)2n−1 xn− yn √ D= (α−β √ D)2n−1 → x2n−Dy2n = (a2−Dβ 2)2n−1 =−1 Ngược lại giả sử (x,y) là một nghiệm của (2.11). Ta có (x+ y √ D)(α+β √ D) = (xα+Dyβ )(yα+ xβ ) √ D = s+ t √ D ở đó s= xα+Dyβ , t = yα+ xβ → s2−Dt2 = (xα+Dyβ )2−D(yα+ xβ )2 35 = (x2−Dy2)(α2−Dβ 2) = (−1)(−1) = 1 Vậy (s, t) là nghiệm của phương trình Pell loại 1 s2−Dt2= 1. Gọi (a,b) là nghiệm nhỏ nhất của nó. Theo công thức nghiệm của phương trình Pell loại 1 và định lý 3 tồn tại n ∈ N∗ sao cho (x+ y √ D)(α+β √ D) = s+ t √ D= (a+b √ D)n = (α2+Dβ 2+2αβ √ D)n = (α+β √ D)2)n = (α+β √ D)2n → x+ y √ D= (α+β √ D)2n−1 = xn+ yn √ D → x= xn,y= yn Một số bài toán chọn lọc Bài toán 2.2.8. Số nguyên dương S được gọi là số Heron nếu nó là diện tích của một tam giác có ba cạnh là ba số nguyên liên tiếp. Chứng minh rằng S là số Heron khi và chỉ khi S khi là số hạng của dãy (Sn),n≥ 1 xác định bởi S0 = 0,S1 = 6,S2 = 84,Sn+2 = 14Sn+1−Sn Lời giải. Gọi S là diện tích của tam giác có ba cạnh là x−1,x,x+1 với x> 2,x ∈ N∗. Theo công thức Heron. S= 1 4 x √ 3(x2−4)→ 16S2 = 3x2(x2−1) (2.14) Vậy S là số Heron khi và chỉ khi phương trình (2.14) có nghiệm nguyên dương(S,x). Dễ thấy x phải chẵn. Đặt x= 2y ta có 16S2 = 3x2(x2−1)⇔ S2 = 3y2(y2−1) → S= y √ 3(y2−1)→ 3(y2 =−1) = h2 36 → h= 3z→ 3(y2−1) = 9z2 → y2−3z2 = 1,S= 3yz Ngược lại nếu (y,z) là nghiệm của phương trình Pell y2−3z2 = 1 (2.15) thì x= 2y,y> 1,S= 3yz là nghiệm của (2.14) Nghiệm nhỏ nhất của (2.15) là (2,1) Vậy tất cả nghiệm của (2.15) (yn,zn) cho bởi yn = (2+ √ 3)n+(2−√3)n 2 zn = (2+ √ 3)n− (2−√3)n 2 √ 3 Do đó Sn= 3ynzn = √ 3 4 ((7+ √ 3)n− (7−4 √ 3)n) → Sn+2 = 14Sn+1−Sn,S0 = 0,S1 = 6,S2 = 84 Bài toán 2.2.9. Tìm tất cả các số nguyên dương n sao cho 2n+1 và 3n+1 đều là số chính phương. Lời giải. Vì (2n+ 1,3n+ 1) = 1 nên 2n+ 1 và 3n+ 1 đều là số chính phương khi và chỉ khi (2n+ 1)(3n+ 1) = y2,y ∈ N∗. Suy ra (12n+ 5)2− 24y2 = 1. Đặt x = 12n+5 ta có x2−24y2 = 1. Gọi (xk,yk) là nghiệm của nó. Nghiệm nhỏ nhất của phương trình Pell này là (5,1). Do đó (xk) cho bởi hệ thức. x0 = 1,x1 = 5,xk+2 = 10xk+1− xk. Dễ chứng minh xk ≡ 5 (mod 12) khi vào chỉ khi k lẻ. Vậy n= nk,k ≥ 1 ở đó nk = x2k+1−5 12 Ta xác định hệ thức truy hồi của dãy (nk) 37 Đặt uk = x2k+1 = 12nk+5. Ta có x2k+3 = 10x2k+2− x2k+1 = 10(10x2k+1− x2k)− x2k+1 = 100x2k+1−10x2k− x2k+1 = 99x2k+1 = x2k+1− x2k−1 = 98x2k+1− x2k−1 → uk+2 = 98uk+1−uk ⇔ 12nk+2+5= 98(12nk+1+5) = 12nk−5 nk+2 = 98nk+1−nk+40 với n1 = 40,n2 = 3960 Bài toán 2.2.10. Cho dãy (xn,yn) xác định như sau (x0,y0) = (0,1),(x1,y1) = (3,5) và  xn+1 = 3xn+2yn+1yn+1 = 4xn+3yn+2 (2.16) Chứng minh rằng (xn,yn) là tất cả các nghiệm nguyên dương của phương trình x2+(x+1)2= y2 Lời giải. Phương trình đã cho tương đương với (2x+1)2−2y2 =−1 (2.17) Đặt u= 2x+1,→ u2−2y2 =−1. Nghiệm nhỏ nhất của phương trình này là (1.1). Do vậy dãy nghiệm (un,yn) cho bởi un = (1+ √ 2)2n+1+(1−√2)2n+1 2 yn = (1+ √ 2)2n+1− (1−√2)2n+1 2 √ 2 Từ đó u0 = 1,u1 = 7,uk+2 = 6uk+1−uk 38 y0 = 1,y1 = 5,yk+2 = 6yk+1− yk Ta có un= 2xk+2+1→ 2xk+2+1= 6(2nk+1+1)−2nk−1→ x0= 0,x1= 3,xk+2= 6xk+1− xk+2. Thành thử dãy nghiệm (xn,yn) của (2.17) cho bởi x0 = 0,x1 = 3,xn+2 = 6xn+1− xn+2 y0 = 1,y1 = 5,yn+2 = 6yn+1 = yk Thành thử ta chỉ cần chứng minh dãy (2.16) thoả mãn quan hệ xn+2 = 6xn+1− xn+2 yn+2 = 6yn+1− yk Thật vậy đặt zn = 2xn+1. Khi đó dễ kiểm tra zn+1 = 3zn+4yn yn+1 = 2zn+3yn → zn+2 = 3zn+1+4yn+1 = 3zn+1+8zn+12yn = 3zn+1+8zn+3zn+1−9zn = 6zn+1− zn → 2xn+2+1= 6(2xn+1+1)−2xn−1 → xn+2 = 6xn+1− xn+2 Tương tự yn+2 = 6yn+1− yk 2.3 Phương trình Pythagoras Trong mục này chúng ta sẽ đi tìm tất cả các nghiệm nguyên dương của phương trình x2+ y2 = z2 (2.18) và xét một số ứng dụng của nó. Những phương trình Diophantine này được gọi là các phương trình Pythagoras. 39 Định nghĩa 2.3.1. Một bộ ba số nguyên dương (x,y,z) thoả mãn phương trình (2.18) gọi là một bộ ba số Pythagoras. Các bộ ba số Pythagora biểu thị độ dài các cạnh của một tam giác vuông. Từ một bộ ba số Pythagoras (x,y,z) nào đó ta suy ra dễ dàng một tập hợp vô hạn các bộ ba số Pythagoras khác (tx, ty, tz) với t là số nguyên dương. Ngược lại, cho (x,y,z) là một bộ ba số Pythagoras bất kỳ và giả sử d = (x,y,z). Khi đó (x1,y1,z1) cũng là một bộ ba số Pythagoras, ở đó x1 = x d , y1 = y d , z1 = z d , và (x1,y1,z1) = 1. Định nghĩa 2.3.2. Một bộ ba số Pythagoras (x,y,z) là nguyên thuỷ nếu (x,y,z)= 1. Rõ ràng từ lý luận trên ta chỉ cần đi tìm các bộ ba số Pythagoras nguyên thuỷ. Dễ dàng nhận thấy nếu (x,y,z) là một bộ ba số Pythagoras nguyên thuỷ thì chúng đôi một nguyên tố cùng nhau. Thật vậy, giả sử d = (x,y). Khi đó d2 là ước của z2 nên d là ước của z do đó d là ước chung của x, y, z. Vậy d = 1. Định lí sau đây cho công thức mô tả tất cả các bộ ba số Pythagoras nguyên thuỷ. Định lí 2.3.3. Giả sử (x,y,z) là một bộ ba số Pythagoras nguyên thuỷ. Khi đó x và y có tính chẵn lẻ khác nhau. Nếu x chẵn, y lẻ chẳng hạn (x,y,z) có dạng x= 2mn, y= m2−n2, n= m2+n2 trong đó m, n là hai số nguyên đương nguyên tố cùng nhau, có tính chẵn lẻ khác nhau. Đảo lại, nếu m, n là hai số nguyên dương nguyên tố cùng nhau, một chẵn, một lẻ thì ba bộ (x,y,z) xác định như trên là một bộ ba số Pythagoras nguyên thuỷ. Chứng minh. Trước hết vì (x,y) = 1 nên x và y không cùng chẵn. Hai số x và y cũng không thể cùng lẻ vì nếu như vậy thì z2 = x2+ y2 ≡ 2 (mod 4), điều này không thể có vì một số chính phương chỉ đồng dư 0 hoặc 1 theo modulo 4. 40 Giả sử x chẵn, y lẻ. Khi đó z lẻ và x2 = z2− y2(z+ y)(z− y), điều này tương đương với (x 2 )2 = ( z+ y 2 )( z− y 2 ) . (2.19) Dễ thấy rằng ( z+y 2 , z−y 2 ) = 1 vì (z,y) = 1. Suy ra tồn tại m, n ∈ N∗ để z+y2 = m2 và z−y 2 = n 2. Từ đó x = 2mn, y = m2− n2, z = m2+ n2. Mặt khác (m2,n2) = 1 nên (m,n) = 1. Hơn nữa vì y và z lẻ nên m, n có tính chẵn lẻ khác nhau. Bây giờ ta chứng minh phần đảo của định trong định lí trên. Dễ dàng kiểm tra rằng x, y, z xác định theo công thức trên là bộ ba số Pythagoras. Ta còn phải chứng minh đó là bộ ba số Pythagoras nguyên thuỷ. Giả sử d = (y,z). Khi đó vì y, z lẻ nên d lẻ. Ta có d | y+ z= 2m2 suy ra d | m2 và d | z− y= 2n2 suy ra d | n2. Vì (m,n) = 1 nên từ đó d = 1. Vậy (y,z) = 1 suy ra (x,y,z) = 1. Định lí được chứng minh. Sau đây là áp dụng quan trọng của Định lí 2.3.3. Định lí 2.3.4. Không tồn tại hai số tự nhiên x và y để tổng các bình phương và hiệu các bình phương của chúng đều là các số chính phương. Chứng minh. Ta chứng minh bằng phản chứng. Giả sử tồn tại các số nguyên dương x, y, có tính chất đã nêu. Trong các cặp số (x,y) ta chọn (x0,y0) là cặp số mà x nhỏ nhất. Giả sửx 2 0+ y 2 0 = z 2 0, x20− y20 = t20 , (2.20) với z0, t0 ≤ N∗. Ta có (x0,y0) = 1. Thật vậy, giả sử d = (x0,y0). Từ (2.20) suy ra d2 | z20 và d2 | t20 . Từ đó d | z0 , d | t0 . Đặt x0 d , y1 = y0 d , z1 = y z0 d , t1 = t0 d . 41 Ta có x21+ y 2 1 = z 2 1, x 2 1− y21 = t21 . Suy ra (x1,y1) là một cặp thoả mãn tính chất đã nêu. Do đó x21+ y 2 1 ≥ x20+ y20 = d(x21+ y21). Vậy d = 1. Từ (2.20) suy ra z20+ t 2 0 = 2x 2 0. Do đó z0 và t0 có cùng tính chẵn lẻ. Đặt u= z0+ t0 2 , v= z0− t0 2 với u, v là các số nguyên dương. Khi đó u+ v= z0, u− v= t0vu2+ v2 = x20. (2.21) Ta có (u,v) = 1, vì nếu d = (u,v) thì d2 | x20. Mặt khác d | u+ v = z0, suy ra d2 | z20− x20 = y20 suy ra d | y0. Vậy d = 1. Theo (2.21) thì (u,v,x0) là một bộ ba số Pythagoras nguyên thuỷ. Theo Định lí 2.3.3 tồn tại các số nguyên dương m, n chẵn lẻ khác nhau với (m,n) = 1, m> n sao cho u= 2mn, v= m2−n2; hoặc u= 2m2−n2, v= 2mn. Trong mọi trường hợp, uv= 2mn(m2−n2). Ta lại có 2y= (u+ v)2− (u− v)2 = 4uv= 8mn(m2−n2) suy ra y= 4mn(m2−n2), tức là y0 = 2k. Vậy mn(m2−n2) = k2. (2.22) Ta có (m,n) = 1 nên (m+n,m) = 1 và (m−n,m) = 1. Vậy (m2−n2,m) = 1. 42 Tương tự, (m2−n2,n) = 1. Do điều này nên từ (2.3) suy ra tồn tại a,b,c ∈ N∗ để m= a2, n= b2, m2−n2 = c2. (2.23) Gọi d = (m+n,m−n). Do m, n chẵn lẻ khác nhau nên m+n, m−n lẻ, từ đó d lẻ. Vì d | m+n, d | m−n nên d | 2m, d | 2n suy ra d | m, d | n (do d lẻ). Suy ra d = 1. Do điều này nên từ (2.23) suy ra tồn tại r, s ∈ N∗ để m−n= r2, m+n= s2. Vậy a2+b2 = s2, a2−b2 = r2, tức là cặp (a,b) thoả mãn tính chất đã nêu trong định lí. Mặt khác a2+b2 = m+n≤ 2m≤ 2mn≤ u= z0+ t0 2 < z0 ≤ z20 = x20 = y20. Điều này trái với cách chọn cặp (x0,y0). Định lí được chứng minh xong. Một số bài toán chọn lọc Bài toán 2.3.5 (Đề dự tuyển thi Toán quốc tế năm 1979). Chứng minh rằng không tồn tại hình chóp tứ giác đều mà các cạnh, diện tích toàn phần và thể tích của nó đều là các số nguyên. Chứng minh. Giả sử g, f , h, S và V theo thứ tự là cạnh đáy, cạnh bên, chiều cao, diện tích toàn phần và thể tích của một hình chóp tứ giác đều và chúng là những số nguyên. Ta có f = √ h2+ g2 2 , V = g2h 3 , S= g2+2g √ h2+ g2 4 . Vì g, S là số nguyên nên 2g √ h2+ g 2 4 là số nguyên. Kí hiệu x= 2g2 √ h2+ g2 4 , y= g3. 43 Dễ thấy x, y ∈ N∗. Ta có x2− y2 = 4g4 ( 22+ g2 4 ) −g6 = 4h2g4 = (2g2h)2 là số chính phương, vì V = g 2h 3 ∈ N∗. Do đó g2 ∈ N∗. Mặt khác, x2+ y2 = 4g4h2+2g6 = 4g4 ( h2+ g2 2 ) = 4g4 f 2 = (2g2 f )2. Vì 2g2 f ∈ N∗ nên x2+ y2 là số chính phương. Song điều này mâu thuẫn với Định lí 2.3.4. Ta có điều cần chứng minh. Bài toán 2.3.6. Chứng minh rằng phương trình x4− y4 = z2 không có nghiệm nguyên dương. Chứng minh. Ta sẽ chứng minh bài toán này bằng phương pháp phản chứng. Giả sử (x,y,z) là nghiệm nguyên dương của phương trình đã cho và d = (x,y). Ta có x= dx0, y= dy0, (x0,y0) = 1. Thay vào phương trình cho ta d4(x40− y40) = z2 suy ra d2 | z. Đặt z= d2z0 suy ra x40− y40 = z20, tức là (x20− y20)(x20+ y20) = z20. Nếu x0 và y0 chẵn lẻ khác nhau thì (x20− y20,x20+ y20) = 1 bởi vì nếu d1 | (x20− y20) và d1 | (x20+ y20) thì d1 | 2y20 và d1 | 2x20. Vậy d1 = 1 (do d1 lẻ). Do đó x20− y20 = a2, x20− y20 = b2, trái với Định lí 2.3.4. Nếu x0 và y0 cùng lẻ thì x20+y 2 0= 2a, x 2 0+y 2 0= 2b Suy ra x 2 0= a+b, y 2 0= a−b. Ta có 4ab= z20 suy ra ab= z 2 1. Vì (x0,y0) = 1 nên (a,b) = 1. Do đó a= a 2 1, b= b 2 1. Vậy a21+b 2 1 = x 2 0, a 2 1−b21 = y20, và điều này mâu thuẫn với Định lí 2.3.4. 44 Bài toán 2.3.7. Chứng minh rằng phương trình x4+ y4 = z2 không có nghiệm nguyên dương. Chứng minh. Giả sử trái lại, phương trình đã cho có nghiệm nguyên dương. Gọi (x0,y0) là nghiệm nguyên dương sao cho tổng x là nhỏ nhất. Lập luận tương tự như trong chứng minh Định lí 2.3.4 ta thấy (x0,y0) = 1. Như vậy (x20,y 2 0,z0) là một bộ ba số Pythagoras nguyên thuỷ. Không làm giảm tổng quát ta giả sử x0 lẻ. Theo Định lí 2.3.3 tồn tại m, n với (m,n) = 1 sao cho{ x= m2−n2, y= 2mn,z0 = m2+n2. (2.24) Vì (m,n) = 1 nên từ (2.24) ta có (x0,n,m) là một bộ ba số Pythagoras nguyên thuỷ. Vậy lại theo Định lí 2.3.3 tồn tại a, b với (a,b) = 1 sao cho{ x0 = a2−b2, n= 2ab,m= a2+b2. (2.25) Ta có y20s= 2mn= 4abm suy ra abm= y 2 1 (ở đây y0 = 2y1) suy ra a= a 2 1, b= b 2 1, m= m2