Luận văn Xấp xỉ diophantine và phân số liên tục trong giải phương trình pell

ng 1, ngoại trừ a0 có thể nhỏ hơn hoặc bằng 0. Ta biểu thị bởi pn giá trị của An, tương tự ta biểu thị bởi qn giá trị Bn cho các giá trị đặc biệt này. Do vậy pn và qn là số nguyên với qn > 0 cho n ≥ 0. Kết quả của bổ đề 1.4 là: pn qn = a0 + b1| |a1 + ...+ bn| |an cho n ≥ 0. Ta suy ra từ (1.7) pn = anpn−1 + bnpn−2, qn = anqn−1 + bnqn−2, cho n ≥ 0. và từ (1.9), pnqn−1 − pn−1qn = (−1)n+1b0...bn, cho n ≥ −1. Có thể viết được, cho n ≥ 1, pn qn − pn−1 qn−1 = (−1)n+1b0...bn qn−1qn . (1.12) Thêm tổng sử dụng (1.11)) ta được tổng: pn qn = a0 + n∑ k=1 (−1)k+1b0...bk qk−1qk . (1.13) 22 Nhắc lại cho các số thực a, b, c, d với b, d là các số dương, ta có: a b < c d ⇒ a b < a+ c b+ d < c d . (1.14) Từ đó an và bn là số dương với n ≥ 0, ta suy ra rằng cho n ≥ 2, số hữu tỷ pn qn = anpn−1 + bnpn−2 anqn−1 + bnqn−2 nằm giữa pn−1 qn−1 và pn−2 qn−2 . Vì vậy, ta có p2 q2 < p4 q4 < ... < p2n q2n < ... < p2m+1 q2m+1 < p3 q3 < p1 q1 . (1.15) Từ (1.12) suy ra, cho n ≥ 3, thì qn−1 > qn−2, do vậy qn > (an + bn)qn−2. Suy luận trên là hợp lệ mà không có bất kì hạn chế nào, giờ ta giả sử an ≥ bn cho tất cả n đủ lớn, nói n ≥ no. Sau đó cho n ≥ n0, sử dụng qn > 2bnqn−2, ta được ∣∣∣pn qn − pn−1 qn−1 ∣∣∣ = b0...bn qn−1qn < bn...b0 2n−n0bnbn−1...bn0+1qn0qn0−1 = bn0...b0 2n−n0qn0qn0−1 , và vế phải tiến dần đến 0 khi n tiến đến vô cùng. Do đó chuỗi (pn/qn)n≥0 có giới hạn, ta biểu diễn bởi x = a0 + b1| |a1 + ...+ bn−1| |an−1 + bn| |an + ... Từ (1.13), x được đưa ra bởi một dãy: x = a0 + ∞∑ k=1 (−1)k+1b0...bk qk−1qk . Bây giờ ta chứng minh rằng x là số vô tỷ. Xác định với n ≥ 0, xn = an + bn+1| |an+1 + ... 23 sao cho x = x0 và cho mọi n ≥ 0, xn = an + bn+1 xn+1 , xn+1 = bn+1 xn − an , và an < xn < an + 1. Do vậy, cho n ≥ 0, xn là số hữu tỷ nếu và chỉ nếu xn+1 là số hữu tỷ, và do đó nếu x hữu tỷ thì tất cả xn với n ≥ 0 là số hữu tỷ. Giả sử x là số hữu tỷ. Xét các số hữu tỷ xn với n ≥ n0 và chọn một giá trị của n mà nếu mẫu số v của xn là tối thiểu, nói xn = u/v. Từ xn+1 = bn+1 xn − an = bn+1v u− anv , với 0 < u− anv < v, sau đó xn+1 có mẫu số nhỏ hơn v, mâu thuẫn. Vì vậy x là số vô tỷ. Ngược lại, cho một số vô tỷ x và một chuỗi b1, b2, ... của số nguyên dương, có duy nhất một số nguyên dương a0 và duy nhất dãy a1, ..., an, ... của số nguyên dương thỏa mãn an ≥ bn cho mọi n ≥ 1, sao cho: x = a0 + b1| |a1 + ...+ bn−1| |an−1 + bn| |an + ... Thât vậy, nghiệm duy nhất được đưa vào theo quy nạp như sau: a0 = bxc, x1 = b1/{x}, và một lần nữa a0, ..., an−1 và x1, ..., xn đã được biết, sau đó an và xn+1 được cho bởi an = bxnc, xn+1 = bn+1/{xn}, sao cho n ≥ 1, ta có 0 < xn − an < 1 và x = a0 + b1| |a1 + ...+ bn−1| |an−1 + bn| |xn . Đây là điều chứng minh. Mệnh đề 1.3. Cho số nguyên a0 và hai chuỗi a0, a1, ... và b1, b2, ... của số nguyên dương với an ≥ bn cho mọi n đủ lớn, phân số liên tục vô hạn a0 + b1| |a1 + ...+ bn−1| |an−1 + bn| |an + ... 24 tồn tại và là số vô tỷ. Ngược lại, cho một số x vô tỷ và một chuỗi b1, b2, ... của số nguyên dương, có duy nhất số nguyên dương a0 ∈ Z và duy nhất chuỗi a1, ..., an, ... của số nguyên dương thỏa mãn an ≥ bn cho mọi n ≥ 1, sao cho x = a0 + b1| |a1 + ...+ bn−1| |an−1 + bn| |an + ... Sau đây là ví dụ khác về chuỗi số nguyên: 1√ e− 1 = 1 + 2| |3 + 4| |5 + 6| |7 + 8| |9 + ... = 1541494082... 1 e− 1 = 1| |1 + 2| |2 + 3| |3 + 4| |4 + ... = 0581976706... Chú ý 1.2. Một biến thể của thuật toán các phân số liên tục đơn giản tiếp theo. Cho hai dãy (an)n≥0 và (bn)n≥0 của các phần tử trong một trường K và một phần tử x trong K, một định nghĩa của chuỗi (có thể hữu hạn)(xn)n≥1 của các phần tử trong K như sau: nếu x = a0, chuỗi rỗng. Nếu không thì x1 được xác định bởi x = a0 + b1/x1. Bằng quy nạp, mỗi x1, ..., xn được xác định, có hai trường hợp: • Nếu xn = an, thuật toán dừng lại. • Cách khác, xn+1 được xác định bởi xn+1 = bn+1 xn − an . Do đó xn = an + bn+1 xn+1 . Nếu thuật toán không dừng lại, thì cho bất kì n ≥ 1, có x = a0 + b1| |a1 + ...+ bn−1| |an−1 + bn| |an Trong trường hợp đặc biệt khi a0 = a1 = ... = b1 = b2 = ... = 1, tập của x sao cho thuật toán dừng sau hữu hạn bước là tập (Fn+1/Fn)n≥1 của thương của các số Fibonacci liên tiếp. Trong trường hợp đặc biệt này, giới hạn của a0 + b1| |a1 + ...+ bn−1| |an−1 + bn| |an 25 là tỉ số Golden, với x độc lập. 1.2.2.2. Phân số liên tục đơn giản Ta đã hạn chế suy luận của mục 1.2.2.1 với trường hợp b1 = b2 = ... = bn = ... = 1. Ta giữ các kí hiệu An và Bn mà đa thức trong Z[a0, a1, ..., an] và Z[a1, ..., an] tương ứng và khi thay đổi đến số nguyên a0, a1, ..., an, ... với an ≥ 1, cho n ≥ 1 ta sử dụng kí hiệu pn và qn cho giá trị của An và Bn. Các mối quan hệ trong (1.7), với n ≥ 0,( An An−1 Bn Bn−1 ) = ( An−1 An−2 Bn−1 Bn−2 )( an 1 1 0 ) . (1.16) Trong khi (1.8) trở thành, cho n ≥ −1,( An An−1 Bn Bn−1 ) = ( ao 1 1 0 )( a1 1 1 0 ) ... ( an−1 1 1 0 )( an 1 1 0 ) . (1.17) Từ bổ đề 1.4, suy ra với n ≥ 0, [a0, ..., an] = An Bn . Lấy định thức trong (1.17), ta suy ra trường hợp đặc biệt của (1.9): AnBn−1 − An−1Bn = (−1)n+1. Sự thay đổi các mối quan hệ này với các giá trị tách rời của a0, a1, a2, ...,( pn pn−1 qn qn−1 ) = ( pn−1 pn−2 qn−1 qn−2 )( an 1 1 0 ) với n ≥ 0, (1.18) ( pn pn−1 qn qn−1 ) = ( ao 1 1 0 )( a1 1 1 0 ) ... ( an−1 1 1 0 )( an 1 1 0 ) với n ≥ −1, [a0, ..., an] = pn qn với n ≥ 0, (1.19) 26 và pnqn−1 − pn−1qn = (−1)n+1 với n ≥ −1. (1.20) Từ (1.20) sau đó với n ≥ 0, phân số pn/qn là thấp nhất: gcd(pn, qn) = 1. Qua (1.19), với n ≥ −1,( pn qn pn−1 qn−1 ) = ( an 1 1 0 )( an−1 1 1 0 ) ... ( a1 1 1 0 )( a0 1 1 0 ) , từ đó ta suy ra, với n ≥ 1, [an, ..., a0] = pn pn−1 và [an, ..., a0] = qn qn−1 . Bổ đề 1.5. Với n ≥ 0, pnqn−2 − pn−2qn = (−1)nan. Chứng minh. Ta nhân cả hai mặt của (1.18) ở bên trái bởi sự nghịch đảo của ma trận:( pn−1 pn−2 qn−1 qn−2 ) , đó là: (−1)n ( qn−2 −pn−2 −qn−1 pn−1 ) . Ta nhận được (−1)n ( pnqn−2 − pn−2qn pn−1qn−2 − pn−2qn−1 −pnqn−1 + pn−1qn 0 ) = ( an 1 1 0 ) .  1.2.2.2.1. Phân số liên tục đơn giản của số hữu tỷ Cho u0 và u1 là hai số nguyên với u1 là số dương. Bước đầu tiên trong thuật toán Euclid để tìm gcd của u0 và u1 bao gồm trong việc chia uo bởi u1. u0 = a0u1 + u2, 27 với a0 ∈ Z và 0 ≤ u2 < u1. Nghĩa là: u0 u1 = a0 + u2 u1 . Với giá trị để chia số hữu tỷ x0 = u0/u1 với thương a0 và phần còn lại u2/u1 < 1. Thuật toán này tiếp tục với um = amum+1 + um+2. Trong đó am là phần không tách rời của xm = um/um+1 và 0 ≤ um+2 < um+1, cho đến khi ul+2 là 0, trong trường hợp các thuật toán dừng lại với ul = alul + 1. Từ đó gcd của um và um+1 giống như gcd của um+1 và um+2, sau gcd của u0 và u1 là ul+1. Đây là cách chính qui để khai triển phân số liên tục x0 = [a0, a1, ..., al], trong đó l = 0 trong trường hợp x0 là số nguyên, trong khi al ≥ 2 nếu x0 là số hữu tỷ không là số nguyên. Mệnh đề 1.4. Bất kì một phân số liên tục hữu hạn một phần [a0, a1, ..., an], trong đó a0, a1, ..., an là số hữu tỷ với ai ≥ 2 cho 1 ≤ i ≤ n và n ≥ 0, thể hiện một số hữu tỷ. Ngược lại, bất kì số hữu tỷ x có hai đại diện như một phân số liên tục, đầu tiên, đưa bởi thuật toán Euclid, là x = [a0, a1, ..., an], và thứ hai là x = [a0, a1, ..., an−1, an − 1, 1]. Nếu x ∈ Z thì n = 0 và hai phân số liên tục đơn giản đại diện của x là [x] và [x− 1, 1], trong khi nếu x không là số nguyên thì n ≥ 1 và an ≥ 2. 28 1.2.2.2.2. Phân số liên tục vô hạn đơn giản của số vô tỷ Cho số nguyên a0 và một dãy vô hạn các số nguyên dương a1, a2, ..., phân số liên tục [a0, a1, ..., an, ...], đại diện cho số vô tỷ. Ngược lại, đưa số vô tỷ x, có biểu diễn duy nhất của x như một phân số liên tục vô hạn đơn giản x = [a0, a1, ..., an, ...]. Các định nghĩa. Các số an là thương riêng, số hữu tỷ pn qn = [a0, a1, ..., an], là các hội tụ và các số xn = [an, an+1, ...], là tỉ số hoàn chỉnh. Từ các định nghĩa này, ta suy ra, với n ≥ 0, x = [a0, a1, ..., an, xn+1] = xn+1pn + pn−1 xn+1qn + qn−1 . (1.21) Bổ đề 1.6. Với n ≥ 0, qnx− pn = (−1) n xn+1qn + qn−1 . Chứng minh. Từ (1.21) suy ra x− qn pn = xn+1pn + pn−1 xn+1qn + qn−1 − pn qn = (−1)n (xn+1qn + qn−1)qn .  Hệ quả 1.2. Cho n ≥ 0, 1 qn+1 + qn < |qnx− pn| < 1 qn+1 . 29 Chứng minh. Từ an+1 là một phần không thiếu của xn+1, ta có an+1 < xn+1 < an+1 + 1. Từ qn+1 = an+1qn + qn−1, ta suy ra qn+1 < xn+1qn + qn−1 < an+1qn + qn−1 + qn = qn+1 + qn.  Đặc biệt, từ xn+1 > an+1 và qn−1 > 0>, một suy luận từ bổ đề 1.6: 1 (an+1 + 2) + q2n < |x− pn qn | < 1 an+1q2n . (1.22) Do đó bất kì hội tụ p/q của x thỏa mãn |x− p/q| < 1/q2. Hơn nữa nếu an+1 lớn, thì xấp xỉ pn/qn là dễ nhận. Do đó, phần lớn thương số tốt cho xấp xỉ hữu tỷ bởi cắt bỏ dạng khai triển phân số liên tục ngay trước khi đưa ra một phần thương nhất định. Ở đây, tác giả đã đưa ra tóm tắt lí thuyết về phân số liên tục, đồng thời ứng dụng lí thuyết phân số liên tục trong giải phương trình Pell khi kết hợp với xấp xỉ hữu tỷ. 1.3. Bài toán ứng dụng Trong mục này, tác giả trình bày một số bài tập sưu tập được qua một số kì thi học sinh giỏi của các năm kèm theo lời giải chi tiết. Nội dung được tham khảo trong tài liệu [2], [3]. Bài toán 1.3. (CANADA). Cho hai dãy số {xn} và {yn} xác định như sau: x0 = 1;x1 = 2;xn+1 = 4xn − xn−1; y0 = 1; y1 = 2; yn+1 = 4yn − yn−1. Chứng minh rằng với mọi số nguyên n ta có: y2n = 3x 2 n + 1. Lời giải: 30 Xét phương trình Pell loại I :X2− 3Y 2 = 1. Phương trình này có nghiệm nhỏ nhất là (2; 1) nên tất cả các nghiệm của phương trình là (Xn;Yn) sao cho: X0 = 1;X1 = 2;Xn+1 = 4Xn −Xn−1; Y0 = 1;Y1 = 2;Yn+1 = 4Yn − Yn−1. Do đó Xn = yn;Yn = xn hay (xn; yn) là nghiệm của phương trình Pell loại I trên. Vậy y2n = 3x 2 n + 1.  Bài toán 1.4.(VMO 1999) Cho hai dãy số {xn} và {yn} xác định như sau: x0 = 1;x1 = 4;xn+2 = 3xn+1 − xn; y0 = 1; y1 = 2; yn+2 = 3yn+1 − yn. Giả sử a, b là các số nguyên dương thỏa mãn a2 − 5b2 + 4 = 0. Chứng minh rằng tồn tại số tự nhiên k để xk = a, yk = b. Lời giải: Xét phương trình Pell x2 − 5y2 = −4. (i) Như ta đã biết , ba dãy số sau vét hết các nghiệm của phương trình (i): x0,1 = 1; y0,1 = 1;xn+1,1 = 9xn,1 + 20yn,1; yn+1,n = 4n,1 + 9n,1, x0,2 = 1; y0,2 = 1;xn+1,2 = 9xn,2 + 20yn,2; yn+2,n = 4n,2 + 9n,2, x0,3 = 1; y0,3 = 1;xn+1,3 = 9xn,3 + 20yn,3; yn+3,n = 4n,3 + 9n,3. Ta chứng minh (xn, yn) cũng vét hết tất cả các nghiệm nguyên dương của (i). Với mọi số tự nhiên n thì n = 3m+r với r = 0; 1; 2. Ta chứng minh (xn, yn) = (xm,r+1; ym,r+1). Ta có: (x0, y0) = (x0,1; y0,1 = (1; 1); (x1, y1) = (x0,2; y0,2 = (4; 2); (x2, y2) = (x0,3; y0,3 = (11; 5). 31 Phương trình đặc trưng của dãy {xn} và {yn} là X2 − 3X + 1 = 0, có hai nghiệm X = 3± √ 5 2 . Nên: xn = x3m+r = α ( 3−√5 2 )3m+r + β ( 3 + √ 5 2 )3m+r = α ( 3−√5 2 )r (9− 4 √ 5)m + β ( 3 + √ 5 2 )r (9 + 4 √ 5)m Đặt um = x3m+r Ta có dãy {um} có phương trình đặc trưng có 2 nghiệm là 9± 4√5 nên: um+1 = 18um − um−1. Suy ra: x3(m+1)+r = 18x3m+r − x3(m−1)+r. (*) Tương tự: y3(m+1)+r = 18y3m+r − y3(m−1)+r. (**) Việc còn lại ta chứng minh {xm,i; ym,i} cũng thỏa mãn (*) và (**) với i = 1; 2; 3. Ta có: xm+1,i = 9xm,i + 20ym,iym+1,i = 4xm,i + 4ym,i ⇒  ym,i = xm+1,i − 9xm, i 20 (a) ym−1,i = xm,i − 9xm−1,i 20 (b) ym,i = 4m−1,i + 9ym−1,i (c) 32 Thế (a), (b) vào (c) ta suy ra: xm+1,i = 18xm,i − xm−1,i và ym+1,i = 18ym,i − ym−1,i. Như vậy {xn} ;{yn} vét hết tất cả các nghiệm của phương trình (i). Do đó luôn tồn tại k để {xk = a} ;{yk = b}.  Bài toán 1.5. (VMO 2012) Xét các số tự nhiên lẻ a, b mà a là ước số của b2 + 2 và b là ước số của a2 + 2. Chứng minh rằng a là các số hạng của dãy số tự nhiên (vn) xác định bởi v1 = v2 = 1 và vn = 4vn−1 − vn − 2, n > 2. Lời giải: Giả sử (a, b) là cặp số tự nhiên mà a là ước số của b2 + 2 và b là ước số của a2 + 2. Trước hết ta chứng minh (a, b) = 1. Thật vậy, đặt d = (a, b) thì d là ước của a và a là ước của b2 + 2 nên d là ước của b2 + 2 suy ra d là ước của 2. Mà a, b lẻ nên d lẻ suy ra d = 1. Xét số N = a2 + b2 + 2 thì do a2 + 2 chia hết cho b nên N chia hết cho b. Vậy tồn tại số nguyên dương k sao cho a2 + b2 + 2 = kab. (i) Tiếp theo ta chứng minh với k = 4. Thật vậy, đặt A = { a+ b|(a, b) ∈ N∗2, a2 + b2 + 2 = kab}. Theo giả sử ở trên thì A 6= ∅. Do tính sắp thứ tự tốt của N,A có phần tử nhỏ nhất. Giả sử a0, b0 là cặp số thỏa mãn điều kiện (i) với a0 + b0 nhỏ nhất. Không mất tính tổng quát, có thể giả sử a0 > b0. Xét phương trình a2 + kb0a+ b 2 0 = 0 có nghiệm a0. Theo định lí Vi-ét thì phương trình trên có một nghiệm nữa là a1kb0 − a0 = b 2 0 + 2 a0 . Theo công thức nghiệm thì rõ ràng a1 nguyên dương. Như vậy (a1, b0) cũng là nghiệm của phương trình (i). Do tính nhỏ nhất của a0 + b0,ta có a0 + b0 6 a1 + b0. Tức là a0 6 kb0 − a0 suy ra a0 b0 6 k 2 Ta có : a20 + b 2 0 + 2 = ka0b0 suy ra a0 b0 + b0 a0 + 2 a0b0 = k. (ii) 33 Do a0 b0 < k 2 và a0 > b0 > 1 nên từ đây ta có k < k 2 + 1 + 2, suy ra k 6 6. Mặt khác áp dụng bất đẳng thức AM-GM, a20 + b 2 0 > 2a0b0. Nên k > 2. Nếu k 6= 4 thì (a0, b0) 6= (1, 1) do đó a0b0 ≥ 2. Lại dùng (ii) để đánh giá, ta có k < 1 2 + 1 + 2, suy ra k 6 4. Vậy các giá trị k = 5, 6 bị loại. Nếu k = 3 thì do a20 + b 2 0 + 2 = 3a0b0, nên suy ra a 2 0 + b 2 0 + 2 chia hết cho 3, suy ra một trong hai số a0 và b0 chia hết cho 3, số còn lại không chia hết cho 3. Nếu b0 = 1 thì a0 chia hết cho 3, khi đó vế trái không chia hết cho 9 còn vế phải chia hết cho 9, mẫu thuẫn. Vậy b0 > 1. Từ đó suy ra a0b0 > 6. Lại sử dụng (ii) để đánh giá ,ta có k 6 k 2 + 1 + 2 6 ⇒ k < 3 8 . Mà k nguyên suy ra k 6 2, mẫu thuẫn. Như vậy ta chứng minh được nếu a, b là các số tự nhiên lẻ thỏa mãn điều kiện đề bài thì: a20 + b 2 0 + 2 = 4ab. (iii) Đặt ẩn phụ z = a− 2b. Phương trình (iii) trở thành: z2 − 3b2 = −2. (iv) Giải phương trình Pell (iv) với tham số n = −2, ta chứng minh được hoàn toàn bài toán.  Nhận xét: Những bài toán trên là các bài toán được sưu tầm từ các đề thi học sinh giỏi toán trong nước và ngoài nước, có kèm theo lời giải giúp bạn đọc thấy được những ứng dụng của phương trình Pell. Qua đó bạn đọc cũng thấy được phương trình Pell nói riêng cũng như phương trình nghiệm nguyên nói chung không có quy tắc giải tổng quát hoặc chỉ có với những dạng đơn giản. Bài tập đề nghị 34 Bài 1.6. (IMO Shorthist) Xét hệ phương trìnhx+ y = z + u2xy = zu Tìm giá trị lớn nhất của hằng số thực m sao cho m ≤ x y với mọi nghiệm nguyên dương (x, y, z, u) của hệ mà x ≥ y. Bài 1.7. Chứng minh rằng nếu 5x2 + 4 hoặc 5x2 − 4 là số chính phương khi và chỉ khi x là số hạng của dãy Fibonacci. Bài 1.8. (Bulgaria 1999). Chứng minh rằng phương trình x2 + y2 + z2 + t2 = 1999 có vô số nghiệm ngyên dương. Bài 1.9. (IMO Shorthist) Chứng minh rằng tồn tại hai dãy số nguyên dương tăng (an), (bn) sao cho an(an + 1) là ước của b 2 n + 1 với mọi n. Kết luận: Trong chương 1, tác giả đã trình bày một cách hệ thống một số khái niệm và kết quả của phương trình Pell cơ bản, hệ thống lí thuyết về phân số liên tục và một số bài toán ứng dụng của phương trình Pell là các bài toán trong các kì thi học sinh giỏi trong nước và ngoài nước. 35 Chương 2 XẤP XỈ DIOPHANTINE, MỞ RỘNG PHƯƠNG TRÌNH PELL VÀ ỨNG DỤNG Trong chương này tác giả sẽ trình bày về hệ thống các bổ đề, hệ quả, mệnh đề về xấp xỉ Diophantine, phân số liên tục trong giải phương trình Pell và ứng dụng của nó. Nội dung được tác giả tham khảo trong tài liệu [4], [5]. 2.1. Chu kì của phân số liên tục Trong mục này tác giả sẽ trình bày bổ đề chính nhằm hỗ trợ trong việc chứng minh các mệnh đề, hệ quả có trong các mục để làm sáng tỏ nội dung chính của chương: các vấn đề về xấp xỉ Diophantine và phân số liên tục, mở rộng của xấp xỉ Diophantine. Nội dung chính được tham khảo trong tài liệu [4]. 36 2.1.1. Bổ đề chính Bổ đề 2.1. Cho  = ±1 và a, b, c, d là số nguyên thỏa mãn: ad− bc = , và d ≥ 1 thì có duy nhất một dãy hữu hạn của các số nguyên a0, ..., as với s ≥ 1 và a1, ..., as−1 dương sao cho:( a b c d ) = ( a0 1 1 0 )( a1 1 1 0 ) ... ( as 1 1 0 ) . (2.1) Các số nguyên này được đặc trưng bởi: b d = [a0, a1, ..., as−1], c d = [as, ..., a1], (−1)s+1 = . (2.2) Ví dụ 2.1. Khi d = 1, cho b và c là các số nguyên,( bc+ 1 b c 1 ) = ( b 1 1 0 )( c 1 1 0 ) , và ( bc− 1 b c 1 ) = ( b− 1 1 1 0 )( 1 1 1 0 )( c− 1 1 1 0 ) . Chứng minh bổ đề 2.1. Với tính duy nhất: Nếu a0, .., as thỏa mãn các kết luận của bổ đề 2.1, thì bằng cách sử dụng (2.1), ta thấy b d = [a0, a1, ..., as−1], c d = [as, ..., a1]. Tiếp theo tính định thức ta có được (−1)s+1 = . Theo sự cố định đẳng thức cuối về tính chẵn lẻ của s và mỗi số hữu tỉ b d , c d có một phần khai triển phân số liên tục mà chiều dài đưa ra tính chẵn lẻ (theo 37 mệnh đề 1.4). Điều này chứng tỏ tính duy nhất của sự phân tích thành nhân tử khi nó tồn tại. Với tính tồn tại. Ta xét dạng khai triển phân số liên tục đơn giản của c d với chiều dài của tính chẵn lẻ đưa ra bởi công thức (2.2) là c d = [as, .., a1]. Cho a0 là số nguyên sao cho khoảng cách giữa b d và [a0, a1, ..., as−1] là nhỏ hơn hoặc bằng 1 2 . Xác định a′, b′, c′, d′ bởi( a′ b′ c′ d′ ) = ( a0 1 1 0 )( a1 1 1 0 ) ... ( as 1 1 0 ) . Ta có d′ > 0, a′d′ − b′c′ = , c ′ d′ = [as, ..., a1] = c d . Từ gcd(c, d) = gcd(c′, d′) = 1, c d = c′ d′ , d > 0, d′ > 0 ta suy ra c′ = c, d′ = d. Từ sự bình đẳng giữa các định thức, ta suy ra a′ = a + kc, b′ = b + kd với một số k ∈ Z và từ b′ d′ − b d = k. Vậy k = 0, (a′, b′, c′, d′) = (a, b, c, d). Do vậy (2.1) được chứng minh.  Hệ quả 2.1. Giả sử các giả thiết của bổ đề 2.1 là thỏa mãn (a)Nếu c > d thì as ≥ 1 và a c = [a0, a1, ..., as]. (b)Nếu b > d thì a0 ≥ 1 và a b = [as, ..., a1, a0]. Ví dụ sau cho thấy giả thiết của hệ quả là không thừa( 1 b 0 1 ) = ( b 1 1 0 )( 0 1 1 0 ) 38 , ( b− 1 b 1 1 ) = ( b− 1 1 1 0 )( 1 1 1 0 )( 0 1 1 0 ) và ( c− 1 1 c 1 ) = ( 0 1 1 0 )( 1 1 1 0 )( c− 1 1 1 0 ) . Chứng minh. Bất kì số hữu tỉ u/v > 1 có hai phân số liên tục. Một trong chúng bắt đầu với 1 chỉ khi u/v = 1 và phân số liên tục là [0, 1]. Do vậy, giả sử c/d bao hàm as > 0. Điều này chứng tỏ phần (a), phần (b) là chuyển vị (hoặc lặp lại chứng minh).  Hệ quả 2.2. Cho a, b, c, d là các số nguyên với ad− bc = ±1 và c > d > 0. Cho x, y là hai số vô tỉ thỏa mãn y > 1 và x = ay + b cy + b . Cho x = [a0, a1, ...] là dạng khai triển phân số liên tục đơn giản của x. Thì tồn tại s ≥ 1 sao cho a = ps, b = ps−1, c = qs, r = qs−1, y = xs+1. Chứng minh. Sử dụng bổ đề 2.1, ta viết( a b c d ) = ( a′0 1 1 0 )( a′1 1 1 0 ) ... ( a′s 1 1 0 ) , với a′1, ..., a ′ s−1 dương và b d = [a′0, a ′ 1, ..., a ′ s−1], c d = [a′s, ..., a ′ 1]. Từ c > d và hệ quả 2.1, ta suy ra a′s > 0 và a c = [a′0, a ′ 1, ..., a ′ s] = p′s q′s , x = p′sy + p ′ s−1 q′sy + q′s−1 = [a′0, ..., a ′ s, y]. Từ y > 1 là a′i = ai, p ′ i = q ′ i với 0 ≤ i ≤ s và y = xs+1.  39 Nhận xét 2.1. Đưa ra các số nguyên a0, a1, ... với ai > 0 cho i ≥ 1 và viết với n ≥ 0, pn qn = [a0, a1, ..., an] ta kiểm tra bởi phương pháp quy nạp trên n, hai công thức:( 1 ao 0 1 )( 1 0 a1 1 ) ... ( 1 an 0 1 ) = ( pn−1 pn qn−1 qn ) nếu n chẵn ( 1 ao 0 1 )( 1 0 a1 1 ) ... ( 1 0 an 1 ) = ( pn pn−1 qn qn−1 ) nếu n lẻ (2.3) Xác định hai ma trận U và L trong GL2(R) của định thức +1 bởi U = ( 1 1 0 1 ) và L = ( 1 0 1 1 ) . Cho p và q trong Z, ta có Up = ( 1 p 0 1 ) và Lq = ( 1 0 q 1 ) . Do đó các công thức (2.3) có dạng: Ua0La1...Lan = ( pn−1 pn qn−1 qn ) nếu n chẵn, và Ua0La1...Lan = ( pn pn−1 qn qn−1 ) nếu n lẻ. Điều liên quan với thuật toán Euclid là: U−p ( a b c d ) = ( a− pc b− pd c d ) và L−q ( a b c d ) = ( a b c− qa d− qb ) . 40 2.1.2. Chu kì phân số liên tục Một dãy số vô hạn ( an ) n≥0 được cho là chu kỳ sau cùng nếu tồn tại n0 ≥ 0 và s ≥ 1 sao cho: an+s = an, (2.4) với mọi n ≥ n0. Tập của s thỏa mãn thuộc tính (2.1.2) là tập bội số dương của số nguyên s0 và (an0, an0+1, ..., an0+s0−1) được gọi là chu kỳ cơ bản. Một phân số liên tục với dãy của các thương số thỏa mãn (2.4) sẽ được viết như sau: [a0, a1, ..., an0−1, an0, ..., an0+s−1]. Ví dụ 2.2. Cho D là số nguyên dương không chính phương, tập a0 = b√Dc, ta có bởi định lý 2.1 a0 + √ D = [2a0, a1, ..., as−1] và 1√ D − a0 = [a1, ..., as−1, 2a0]. Bổ đề 2.2. (Euler, 1737 ). Nếu phân số vô hạn liên tục x = [a0, a1, ..., an, ...] là chu kỳ sau cùng, thì x là số vô tỷ bậc hai. Chứng minh. Từ phân số liên tục của x là vô hạn, x là số vô tỷ. Giả sử đầu tiên phân số liên tục là chu kì, trong (2.4) với n0 = 0, x = [a0, ..., as−1]. Ta có thể viết x = [a0, ..., as−1, x]. Do vậy x = ps−1x+ ps−2 qs−1x+ qs−2 . Suy ra qs−1x2 + (qs−2 − ps−1)x− ps−2, 41 là một đa thức bậc hai khác không với hệ số nguyên có x như là nghiệm a. Vì x là số vô tỷ, đa thức này không rút gọn và x là bậc hai. Trong trường hợp tổng quát tại (2.4) với n0 > 0,ta viết: x = [a0, a1, ..., an0−1, an0, ..., an0+s−1] = [a0, a1, ..., an0−1, y], với y = [an0, ..., an0+s−1] là chu kì phân số liên tục, vì vậy x là bậc hai. Nhưng x = pn0−1 + pn0−2 qn0−1 + qn0−2 , do vậy x ∈ Q(y) là số vô tỷ bậc hai.  Bổ đề 2.3. (Lagrange, 1770) Nếu x là số vô tỷ bậc hai thì phân số liên tục x = [a0, a1, ..., an, ...] là chu kì sau cùng. Chứng minh. Cho n ≥ 0, xác định dn = qnx− pn. Theo hệ quả 1.2, ta có | dn |< 1 qn+1 . Ax2 + Bx + C với A > 0 là đa thức bậc hai không rút gọn có x là nghiệm. Với n ≥ 2, ta suy ra từ (1.21) rằng hội tụ xn là nghiệm của đa thức bậc hai Anx 2 +Bnx+ Cn với An = Ap 2 n−1 +Bpn−1qn−1 + Cq 2 n−1, Bn = 2Apn−1pn−2 +B(pn−1qn−2 + pn−2qn−1) + 2Cqn−1qn−2, Cn = An−1. Cho Ax2 +Bx+ C = 0, ta suy ra: An = (2Ax+B)dn−1qn−1 + Ad2n−1, Bn = (2Ax+B)(dn−1qn−2 + dn−2qn−1) + 2Adn−1dn−2, có công thức tương tự biểu diễn A,B,C như tổ hợp tuyến tính đồng nhất của An, Bn, Cn và từ (A,B,C) 6= (0, 0, 0) ta có (An, Bn, Cn) 6= (0, 0, 0). Từ khi xn là số vô tỷ, suy ra An 6= 0. Từ bất đẳng thức qn−1 | dn−2 |< 1, qn−2 | dn−1 |< 1, qn−1 < qn, | dn−1dn−2 |< 1, 42 suy ra max{|An|, |Bn/2, |Cn|} < A+ |2Ax+B|. Điều này cho thấy |An|, |Bn|, |Cn| là giới hạn độc lập của n. Bởi vậy tồn tại n0 ≥ 0 và s > 0 sao cho xn0 = xn0+s. Từ đó ta suy ra phân số liên tục của x là chu kì sau cùng.  Bổ đề 2.4. Một phân số liên tục x = [a0, a1, ..., an...], là chu kì tuần hoàn khi và chỉ khi x là số vô tỷ bậc hai giảm. Trong trường hợp này, nếu x = [a0, a1, ..., as−1] và nếu x′ là liên hợp Galois của x thì −1/x′ = [as−1, ..., a1, a0]. Chứng minh. Giả sử phân số liên tục của x là chu kì tuần hoàn x = [a0, a1, ..., as−1]. Từ as = a0 ta suy ra a0 > 0, do vậy x > 1. Từ x = [a0, ..., as−1] và tính duy nhất của dạng khai triển phân số liên tục ta suy ra x = ps−1x+ ps−2 qs−1x+ qs−2 và x = xs, do đó x là nghiệm của đa thức bậc hai Ps(x) = qs−1x2 + (qs−2 − ps−1)x− ps−2. Đa thức Ps này có nghiệm dương, cụ thể x > 1 và nghiệm âm x ′ với kết quả xx′ = −ps−2/qs−1. Ta hoán vị mối quan hệ( ps−1 ps−2 qs−1 qs−2 ) = ( a0 1 1 0 )( a1 1 1 0 ) ... ( as−1 1 1 0 ) và có được( ps−1 qs−1 ps−2 qs−2 ) = ( as−1 1 1 0 ) ... ( a1 1 1 0 )( a0 1 1 0 ) . 43 Định nghĩa như sau y = [as−1, ..., a1, a0], để y > 1, y = [as−1, ..., a1, a0, y] = ps−1y + qs−1 ps−2y + qs−2 , và y là nghiệm dương của đa thức Qs(x) = ps−2x2 + (qs−2 − ps−1)x− qs−1. Đa thức Ps, Qs có quan hệ bởi Qs(x) = −x2Ps(−1/x). Do vậy y = −1/x′. Ngược lại, giả sử x > 1 và −1 < x′ < 0. Cho (xn)n≥1 là dãy các thương số hoàn chỉnh của x. Cho n ≥ 1, xác định x′n như liên hợp Galois của xn. Bằng quy nạp suy ra x′n = an + 1/x ′x′n+1 và −1 < x′n < 0( do vậy xn giảm) và an là phần nguyên của −1/x′n+1. Nếu khai triển phân số liên tục của x là chu kì không tuần hoàn, ta có x = [a0, ..., ah−1, ah, ..., ah+s−1], với ah−1 6= ah+s−1. Bằng tính chu kì ta có xh = [ah, ..., ah+s−1, xh], do vậy xh = xh+s, x ′ h = x ′ h+s. Từ x ′ h = x ′ h+s lấy phần nguyên, ta suy ra ah−1 = ah+s−1, mâu thuẫn.  Hệ quả 2.3. Nếu r > 1 là số hữu tỷ không chính phương thì khai triển phân số liên tục của √ r có dạng √ r = [a0, a1, ..., as−1, 2a0], với a1, ..., as−1 có vai trò như nhau và a0 = b √ rc. Ngược lại, nếu khai triển phân số liên tục của số vô tỷ t > 1 có dạng t = [a0, a1, ..., as−1, 2a0], với a1, ..., as−1 có vai trò như nhau thì t2 là số hữu tỷ. Chứng minh.