Giáo trình lý thuyết số

tố của s đều là ước nguyên tố của b. Thế thì có số nguyên dương N sao cho s | bN . Như vậy bNα = bNr/s = ar, trong đó a là số nguyên dương. Vì mỗi số nguyên dương đều có biểu diễn trong cơ số b nên ta giả sử ar có biểu diễn là (amam−1...a1a0)b. Suy ra α = ar/bN = amb m + am−1bm−1 + · · ·+ a1b + a0 bN = (0.00...amam−1...a1a0)b, và như vậy α có biểu diễn hữu hạn trong cơ số b.
Chú ý rằng, số có biểu diễn hữu hạn trong cơ số b, (.c1c2c3...cn)b có thể viết dưới dạng (.c1c2...cn−1anan+1an+2...)b , với an = cn− 1, an+1 = an+2 = · · · = b−1. Chẳng hạn, số (.12)10 = (.119999...)10. Hạn chế được đưa ra trong định lý 7.1 cốt để cho biểu diễn là duy nhất. Biểu diễn vô hạn (.c1c2c3...)b trong cơ số b, được gọi là tuần hoàn nếuu có các số nguyên dương N và k øsao cho cn+k = cn với mọi n ≥ N. Đối với số tuần hoàn như thế, ta viết (.c1c2c3...cN−1cN ...cN+k−1)b . Khi N và k là nhỏ nhất thoả mãn cn+k = cn với mọi n ≥ N, ta nói (.c1c2c3...cN−1)b là tiền chu kỳ và (cN ...cN+k−1)b là chu kỳ. Chẳng hạn, trong hệ thập phân, số 1/6 = (.16¯6)10 có phần trước chu kỳ là 1 và chu kỳ là 6. Định lý sau đây nói lên rằng các số hữu tỉ chính là các số thực có biểu diễn hữu hạn hoặc tuần hoàn trong cơ số b. Định lý 7.3. Giả sử b là số nguyên lớn hơn 1. Thế thì biểu diễn tuần hoàn trong cơ số b là số hữu tỉ. Ngược lại, số hữu tỉ có biểu diễn trong cơ số b là hữu hạn hoặc tuần hoàn. Hơn nữa, nếu 0 < α = r/s < 1 vớir, s là các số nguyên dương nguyên tố cùng nhau và s = TU sao cho (U, b) = 1 và các ước nguyên tố của T đều là ước của b thì biểu diễn của α trong cơ số b có độ dài chu kỳ bằng ordUb và độ dài tiền chu kỳ bằng N, trong đó N là số nguyên dương nhỏ nhất mà T | bN . Chứng minh. ′′ ⇒′′ . Giả sử α = (.c1c2c3...cNcN+1...cN+k)b. Thế thì α = c1 b + c2 b2 + · · ·+ cN bN + ( ∞∑ j=0 1 bjk )(cN+1 bN+1 + · · ·+ cN+k bN+k ) 7.1. SỐ B-PHÂN 101 = c1 b + c2 b2 + · · ·+ cN bN + ( bk bk − 1 )(cN+1 bN+1 + · · ·+ cN+k bN+k ) , và đây là số hữu tỉ. ′′ ⇐′′ . Giả sử 0 < α = r/s < 1 với r, s là các số nguyên dương nguyên tố cùng nhau và s = TU sao cho (U, b) = 1 và các ước nguyên tố của T đều là ước của b. Khi đó có số nguyên dương nhỏ nhất N để T | bN . Đặt bN = aT, với a là số nguyên dương. Trường hợp U = 1 thì α có biểu diễn trong cơ số b là hữu hạn, nhờ định lý 7.2. Xét trường hợp U > 1. Ta có bNα = bN r TU = ar U = A + C U , với A,C là các số nguyên, 0 ≤ A < bN , 0 < C < U và (C,U) = 1. Giả sử A = (anan−1...a1a0)b. Trường hợp U = 1 thì α có biểu diễn trong cơ số b là hữu hạn, nhờ định lý 7.2. Đặt ν = ordUb, ta có b ν = tU + 1 (mod U) với t là số nguyên nào đó. Vậy bν C U = (tU + 1)C U = tC + C U . Nhưng ta có biểu diễn C/U = (.c1c2c3...)b, với cm = [bγm−1], γm = bγm−1 − [bγm−1], với γ0 = C/U, nên bν C U = bν (c1 b + c2 b2 + · · ·+ cν bν + γν bν ) = ( c1b ν−1 + c2bν−2 + · · ·+ cν ) + γν . Suy ra γν = C/U = γ0. Do đó ta có C U = (.c1c2...cν)b. Suy ra bNα = (anan−1...a1a0.c1c2...cν)b, hay α = (.00...anan−1...a1a0c1c2...cν)b, (chuyển dấu chấm trong bNα sang trái N vị trí ). Bây giờ ta còn phải chứng tỏ rằng tiền chu kỳ có độ dài bằng N và độ dài chu kỳ bằng ν. Giả sử α = (.c1c2...cMcM+1...cM+k)b. Thế thì α = c1 b + c2 b2 + · · ·+ cM bM + ( bk bk − 1 )(cM+1 bM+1 + · · ·+ cM+k bM+k ) 102 7. SỐ B- PHÂN. PHÂN SỐ LIÊN TỤC = (c1b M−1 + c2bM−2 + · · ·+ cM)(bk − 1) + (cM+1bk−1 + · · ·+ cM+k ) bM(bk − 1). Vì α = r/s và (r, s) = 1 nên s | bM(bk − 1). Suy ra T | bM và U | (bk − 1). Vậy M ≥ N và ν | k.
Chúng ta có thể áp dụng định lý trên để tìm độ dài của tiền chu kỳ và độ dài chu kỳ trong biểu diễn thập phân. Nếu 0 < α = r/s < 1 và (r, s) = 1, s = 2s15s2t, (t, 10) = 1 thì tiền chu kỳ có độ dài là N = max{s1, s2} và chu kỳ có độ dài là ordt10. Ví dụ 7.1.2. Với số α = 5/28 ta có 28 = 22 · 7 nên trong hệ thập phân, số 5/28 có biểu diễn tuần hoàn với tiền chu kỳ có độ dài bằng 2 và chu kỳ có độ dài bằng ord710 = 6, 5/28 = (.17857142).  Cũng do định lý trên, nếu α có biểu biễn b phân vô hạn không tuần hoàn thì α là số vô tỉ. Ví dụ 7.1.3. Số α = .101001000100001000001... là vô hạn không tuần hoàn nên α là số vô tỉ.  7.2 Phân số liên tục hữu hạn Bằng cách sử dụng thuật toán Euclid, chúng ta có thể biểu diễn các số hữu tỉ như là các phân số liên tục hữu hạn. Ví dụ 7.2.1. Xét số hữu tỷ 62/23. Vì 62 = 23 · 2 + 16 23 = 16 · 1 + 7 16 = 7 · 2 + 2 7 = 2 · 3 + 1 2 = 1 · 2 , nên 62 23 = 2 + 16 23 = 2 + 1 23/16 7.2. PHÂN SỐ LIÊN TỤC HỮU HẠN 103 23 16 = 1 + 7 16 = 1 + 1 16/7 16 7 = 2 + 2 7 = 2 + 1 7/2 7 2 = 3 + 1 2 . Suy ra 62 23 = 2 + 1 23/16 = 2 + 1 1 + 1 16/7 = 2 + 1 1 + 1 2 + 1 7/2 = 2 + 1 1 + 1 2 + 1 3 + 1 2 . Vậy số 62/23 được biểu diễn dưới dạng phân số liên tục hữu hạn: 62 23 = 2 + 1 1 + 1 2 + 1 3 + 1 2  Phân số liên tục hữu hạn, ký hiệu [a0; a1, ..., an−1, an], là biểu thức dạng a0 + 1 a1 + 1 . . . + 1 an−1 + 1 an 104 7. SỐ B- PHÂN. PHÂN SỐ LIÊN TỤC trong đó a0, a1, ..., an−1, an là các số thực với a1, ..., an là các số dương. Phân số liên tục được gọi là đơn giản nếuu a0, a1, ..., an−1, an là các số nguyên. Định lý 7.4. Phân số liên tục hữu hạn đơn giản biểu diễn số hữu tỉ. Chứng minh. Ta sẽ chứng minh bằng qui nạp theo k rằng phân số liên tục hữu hạn đơn giản [a0; a1, ..., ak] biểu diễn số hữu tỉ. Khi k = 0, hiển nhiên rằng a0 là số hữu tỉ. Xét phân số liên tục hữu hạn đơn giản [a0; a1, ..., ak, ak+1]. Ta có [a0; a1, ..., ak, ak+1] = a0 + 1 [a1; ..., ak, ak+1] . Theo giả thiết qui nạp thì [a1; ..., ak, ak+1] là số hữu tỉ, từ đó ta suy ra [a0; a1, ..., ak, ak+1] = a0 + 1 [a1; ..., ak, ak+1] là số hữu tỉ.
Bây giờ chúng ta sẽ chỉ ra rằng mọi số hữu tỉ đều biểu diễn được dưới dạng phân số liên tục hữu hạn đơn giản. Định lý 7.5. Mọi số hữu tỉ đều biểu diễn được dưới dạng phân số liên tục hữu hạn đơn giản. Chứng minh. Giả sử x = a/b, với a, b là các số nguyên và b > 0. Đặt r0 = a và r1 = b. Thuật toán Euclid cho ta r0 = r1q0 + r2 với 0 < r2 < r1 , r1 = r2q1 + r3 với 0 < r3 < r2 , . . . rn−2 = rn−1qn−2 + rn với 0 < rn < rn−1 , rn−1 = rnqn−1 trong đó các q1, q2, ..., qn−1 là các số nguyên dương. Thế thì a b = r0 r1 = q0 + r2 r1 = q0 + 1 r1/r2 r1 r2 = q1 + r3 r2 = q1 + 1 r2/r3 7.2. PHÂN SỐ LIÊN TỤC HỮU HẠN 105 . . . rn−2 rn−1 = qn−2 + rn rn−1 = qn−2 + 1 rn−1/rn rn−1 rn = qn−1. Suy ra a/b được biểu diễn dưới dạng phân số liên tục hữu hạn: a/b = [q0; q1, q2, ..., qn−1].
Cần chú ý rằng, phân số liên tục của số hữu tỉ là không duy nhất. Từ đẳng thức an = (an − 1) + 1 1 ta có [a0; a1, ..., an−1, an] = [a0; a1, ..., an−1, an − 1, 1] khi an > 1. Với k là số nguyên không âm không vượt quá n thì ta nói phân số liên tục [a0; a1, a2, ..., ak] là giản phân thứ k, ký hiệu Ck, của phân số liên tục [a0; a1, a2, ..., an]. Định lý 7.6. Giả sử a0, a1, a2, ..., an là các số thực với a1, a2, ..., an là các số dương và dãy các số p0, p1, p2, ..., pn, q0, q1, q2, ..., qn được xác định bởi p0 = a0 q0 = 1 p1 = a0a1 + 1 q1 = a1 và pk = akpk−1 + pk−2 qk = akqk−1 + qk−2 với mọi k = 2, 3, ..., n. Thế thì giản phân thứ k , Ck = [a0; a1, ..., ak] thoả Ck = pk/qk. 106 7. SỐ B- PHÂN. PHÂN SỐ LIÊN TỤC Chứng minh. Chúng ta chứng minh bằng qui nạp. Khi k = 0 ta có C0 = a0 = a0/1 = p0/q0. Khi k = 1 ta cũng có C1 = [a0; a1] = a0 + 1 a1 = a0a1 + 1 a1 = p1 q1 . Khi k = 2 ta cũng có C2 = [a0; a1, a2] = a0 + 1 a1 + 1 a2 = a0 + a2 a1a2 + 1 = a2(a0a1 + 1) + a0 a2a1 + 1 = p2 q2 . Bây giờ ta giả sử khẳng định đúng cho số tự nhiên k, với 2 ≤ k < n. Vì Ck = [a0; a1, ..., ak] = pk qk = akpk−1 + pk−2 akqk−1 + qk−2 và pk−1, pk−2, qk−1, qk−2 không phụ thuộc vào ak nên ta có Ck+1 = [a0; a1, ..., ak, ak+1] = [a0; a1, ..., ak−1, ak + 1 ak+1 ] = (ak + 1/ak+1)pk−1 + pk−2 (ak + 1/ak+1)qk−1 + qk−2 = ak+1(akpk−1 + pk−2) + pk−1 ak+1(akqk−1 + qk−2) + qk−1 = ak+1pk + pk−1 ak+1qk + qk−1 = pk+1 qk+1 .
Ví dụ 7.2.2. Với phân số liên tục [3; 6, 1, 7] = 173/55, ta có p0 = 3 q0 = 1 p1 = 6 · 3 + 1 = 19 q1 = 6 p2 = 1 · 19 + 3 = 22 q2 = 1 · 6 + 1 = 7 p3 = 7 · 22 + 19 = 173 q3 = 7 · 7 + 6 = 55 . 7.2. PHÂN SỐ LIÊN TỤC HỮU HẠN 107 Thế thì C0 = p0/q0 = 3/1 = 3 C1 = p1/q1 = 19/6 C2 = p2/q2 = 22/7 C3 = p3/q3 = 173/55.  Định lý 7.7. Giả sử Ck = pk, qk, 1 ≤ k ≤ n là giản phân thứ k của phân số liên tục [a0; a1, ..., an] và pk, qk được xác định trong định lý 7.6 thì pkqk−1 − pk−1qk = (−1)k−1. Chứng minh. Với k = 1 ta có p1q0 − p0q1 = (a1a0 + 1) · 1− a0a1 = 1. Giả sử khẳng định đã đúng cho k với 1 ≤ k < n. Thế thì pk+1qk − pkqk+1 = (ak+1pk + pk−1)qk − pk(ak+1qk + qk−1) = −(pkqk−1 − pk−1qk) = (−1)k+1.
Hệ quả 7.7.1. Giả sử Ck = pk, qk, 1 ≤ k ≤ n là giản phân thứ k của phân số liên tục đơn giản [a0; a1, ..., an]; pk, qk được xác định trong định lý 7.6 thì pk và qk là nguyên tố cùng nhau. Chứng minh. Dễ, dành cho đọc giả.
Hệ quả 7.7.2. Giả sử Ck = pk, qk, 1 ≤ k ≤ n là giản phân thứ k của phân số liên tục [a0; a1, ..., an]; pk, qk được xác định trong định lý 7.6 thì Ck − Ck−1 = (−1) k−1 qkqk−1 với 1 ≤ k ≤ n. Cũng vậy Ck − Ck−2 = (−1) kak qkqk−2 với 2 ≤ k ≤ n. 108 7. SỐ B- PHÂN. PHÂN SỐ LIÊN TỤC Chứng minh. Theo định lý 7.6 ta có Ck − Ck−1 = pk qk − pk−1 qk−1 = pkqk−1 − pk−1qk qkqk−1 = (−1)k−1 qkqk−1 Ta cũng có Ck − Ck−2 = (Ck − Ck−1) + (Ck−1 − Ck−2) = (−1) k−1 qkqk−1 + (−1)k−2 qk−1qk−2 = = (−1)k qk−1 ( 1 qk−2 − 1 qk ) = (−1)k qk−1 · qk − qk−2 qkqk−2 = (−1)k qk−1 · akqk−1 qkqk−2 = (−1)kak qkqk−2
Định lý 7.8. Giả sử Ck, 0 ≤ k ≤ n, là giản phân thứ k của phân số liên tục [a0; a1, ..., an]. Thế thì C1 > C3 > C5 > · · · , C0 < C2 < C4 < · · · , và mỗi giản phân thứ lẻ C2j+1 đều lớn hơn giản phân thứ chẵn C2i. Chứng minh. Vì hệ quả 7.7.2 nên với k = 2, 4, 6, ... ta có Ck − Ck−2 = (−1) kak qkqk−1 , suy ra Ck < Ck−2 nếu k lẻ và Ck < Ck−2 nếu k chẵn. Cũng theo hệ quả 7.7.2 ta có C2m+1 − C2m = (−1) 2m q2mq2m−1 > 0, cũng vậy C2m+1 > C2m. Do đó, nếu 2j + 1 > 2i thì C2j+1 > C2j ≥ C2i. Còn nếu 2j+1 C2i vì C2j+1 > C2i+1 và C2i+1 > C2i.
7.3 Phân số liên tục vô hạn Định lý 7.9. Giả sử rằng chúng ta có dãy vô hạn các số nguyên a0, a1, a2, .... với a1, a2, .... là các số dương và Ck = [a0; a1, a2, ..., ak]. Thế thì dãy số C1, C2, C3, ... là hội tụ. 7.3. PHÂN SỐ LIÊN TỤC VÔ HẠN 109 Chứng minh. Từ định lý 7.8 ta có dãy số C1, C3, C5, ... là đơn điệu giảm và bị chặn dưới; cũng vậy, dãy số C0, C2, C4, ... là đơn điệu tăng và bị chặn trên. Thế thì các dãy số C1, C3, C5, ... và C0, C2, C4, ... là hội tụ. Đặt lim n→∞ C2n+1 = α1 và lim n→∞ C2n = α2. Theo hệ quả 7.7.2 ta có C2n+1 − C2n = (−1) 2n q2n+1q2n = 1 q2n+1q2n . Nhưng với định nghĩa của qk trong định lý 7.6 với các số a1, a2, a3, ... là nguyên dương, thì dễ dàng suy ra rằng qk ≥ k. Từ đó ta có 0 < C2n+1 − C2n = 1 q2n+1q2n ≤ 1 (2n + 1)2n . Vậy lim n→∞ (C2n+1 − C2n) = 0, hay lim n→∞ C2n+1 = lim n→∞ C2n.
Giới hạn của dãy số Ck trong định lý trên được xem như là phân số liên tục vô hạn [a0; a1, a2, a3, ... ]. Định lý 7.10. Giả sử rằng a0, a1, a2, .... là dãy vô hạn các số nguyên với a1, a2, .... là các số dương. Thế thì [a0; a1, a2, a3, ... ] là số vô tỉ. Chứng minh. Giả sử α = [a0; a1, a2, a3, ... ] và Ck = pk/qk = [a0; a1, ..., ak]. Khi n là số nguyên dương, từ định lý 7.9 thì C2n < α < C2n+1, hay cũng vậy 0 < α− C2n < C2n+1 − C2n = 1 q2n+1q2n , điều này kéo theo 0 < αq2n − p2n < 1 q2n+1 . 110 7. SỐ B- PHÂN. PHÂN SỐ LIÊN TỤC Giả sử α = a/b là số hữu tỉ, b > 0. Thế thì 0 < aq2n − bp2n < b q2n+1 , điều này không thể xảy ra vì aq2n − bp2n là số nguyên và khi q2n+1 > b.
Định lý 7.11. Giả sử α0 = α là số vô tỉ và dãy số a0, a1, a2, ... được xác định bởi ak = [αk] , αk+1 = 1/(αk − ak) trong đó k = 0, 1, 2, .... Thế thì α là trị của phân số liên tục đơn giản vô hạn [a0; a1, a2, ... ]. Chứng minh. Vì ak = [α] là số nguyên và αk là số vô tỉ nên ta có 1 < αk+1 = 1/(αk − ak) là số vô tỉ. Như vậy ta có dãy vô hạn các số nguyên a0, a1, a2, ... với a1, a2, a3, ... là dương. Từ αk+1 = 1/(αk − ak), ta suy ra αk = ak + 1 αk+1 . Do đó α = α0 = a0 + 1 α1 = [a0;α1] = a0 + 1 a1 + 1 α2 = [a0;α1, α2] . . . = a0 + 1 a1 + 1 . . . + 1 ak + 1 αk+1 = [a0; a1, ..., ak, αk+1]. Như vậy α = [a0; a1, ..., ak, αk+1] = αk+1pk + pk−1 αk+1qk + qk−1 . 7.3. PHÂN SỐ LIÊN TỤC VÔ HẠN 111 Đặt Ck = [a0; a1, ..., ak] là giản phân thứ k của phân số liên tục vô hạn [a0; a1, a2, ... ], ta có α− Ck = αk+1pk + pk−1 αk+1qk + qk−1 − pk qk = −(pkqk−1 − pk−1qk) (αk+1qk + qk−1)qk = (−1)k (αk+1qk + qk−1)qk . Vì αk+1qk + qk−1 > ak+1qk + qk−1 = qk+1, nên | α− Ck |=| (−1) k (αk+1qk + qk−1)qk |< 1 qkqk+1 ≤ 1 k(k + 1) . Vậy α = [a0; a1, a2, ... ].
Ví dụ 7.3.1. Với số α = √ 6, ta có a0 = [ √ 6] = 2, α1 = 1√ 6− 2 = √ 6 + 2 2 , a1 = [ √ 6 + 2 2 ] = 2, α2 = 1 ( √ 6+2 2 )− 2 = √ 6 + 2, a2 = [ √ 6 + 2] = 4, α3 = 1 ( √ 6 + 2)− 4 = √ 6 + 2 2 = α1. Vì α3 = α1, nên a3 = a1, a4 = a2, .... Do đó √ 6 = [2; 2, 4, 2, 4, 2, 4, ... ].  Định lý 7.12. Nếu hai phân số liên tục đơn giản vô hạn [a0; a1, a2, ... ] và [b0; b1, b2, ... ] biểu diễn cùng một số vô tỉ thì ak = bk với mọi k = 0, 1, 2, .... Chứng minh. Giả sử rằng α = [a0; a1, a2, ...]. Thế thì C0 = a0, C1 = a0+1/a1, và theo định lý 7.9 thì a0 < α < a0 + 1/a1, 112 7. SỐ B- PHÂN. PHÂN SỐ LIÊN TỤC như vậy a0 = [α]. Do đó α = lim k→∞ [a0; a1, a2, ..., ak] = lim k→∞ (a0 + 1 [a1; a2, ..., ak] = a0 + 1 lim k→∞ [a1; a2, ..., ak] = a0 + 1 [a1; a2, ... ] . Như vậy: nếu α = [a0; a1, a2, ... ] = [b0; b1, b2, ... ] thì a0 = b0 và [a1; a2, ... ] = [b1; b2, ... ]. Bây giờ ta giả sử rằng ak = bk và [ak+1; ak+2, ... ] = [bk+1; bk+2, ... ]. Lập luận tương tự như trên ta sẽ có ak+1 = bk+1 và ak+1 + 1 [ak+2; ak+3, ... ] = bk+1 + 1 [bk+2; bk+3, ... ] , điều này lại kéo theo [ak+2; ak+3, ... ] = [bk+2; bk+3, ... ].
Giản phân của phân số liên tục đơn giản vô hạn là xấp xỉ tốt nhất của số vô tỉ α. Hệ quả của định lý sau đây sẽ chính xác hoá khái niệm này. Định lý 7.13. Giả sử α là số vô tỉ và pk/qk là giản phân thứ k của phân số liên tục đơn giản vô hạn của α. Nếu r, s là các số nguyên với s > 0 sao cho |sα− r| < |qkα− pk| thì s ≥ qk+1. Chứng minh. Giả sử |sα − r| < |qkα − pk| nhưng 1 ≤ s < qk+1. Xét hệ hai phương trình { pkx + pk+1y = r qkx + qk+1y = s. 7.3. PHÂN SỐ LIÊN TỤC VÔ HẠN 113 Nhân phương trình thứ nhất với qk và phương trình thứ hai với (−pk) rồi cộng lại, ta có (pk+1qk − pkqk+1)y = rqk − spk. Vì pk+1qk − pkqk+1 = (−1)k nên y = (−1)k(rqk − spk). Tương tự, ta có x = (−1)k(spk+1 − rqk+1). Nếu x = 0 thì spk+1 = rqk+1, do (pk+1 = qk+1) = 1, ta suy ra qk+1 | s, vô lý với điều ta giả sử 1 ≤ s < qk+1; vậy |x| ≥ 1. Nếu y = 0, từ các phương trình ta có r = pkx và s = qkx, như vậy |sα− r| = |x| |qkα− pk| ≥ |qkα− pk|, và cũng vô lý với giả thiết |sα− r| < |qkα− pk|; vậy y = 0. Chúng ta sẽ chỉ ra rằng x và y là trái dấu. Trường hợp y < 0, do qkx = s − qk+1y nên x > 0. Trường hợp y > 0, do qk+1y = qk+1 > s và qkx = s− qk+1y nênx < 0. Do α nằm giữa pk/qk và pk+1/qk+1 nên qkα − pk và qk+1α − pk+1 là trái dấu. Từ hệ phương trình ta suy ra |sα− r| = |x(qkα− pk) + y(qk+1α− pk+1)|. Nhưng x(qkα− pk) và y(qk+1α− pk+1) là cùng dấu, nên |sα− r| = |x(qkα− pk)|+ |y(qk+1α− pk+1)| ≥ |x| |qkα− pk| ≥ |qkα− pk|.
Hệ quả 7.13.1. Giả sử α là số vô tỉ và pk/qk là giản phân thứ k của phân số liên tục đơn giản vô hạn của α. Nếu r, s là các số nguyên với s > 0 sao cho |α− r/s| < |α− pk/qk| thì s > qk. 114 7. SỐ B- PHÂN. PHÂN SỐ LIÊN TỤC Chứng minh. Giả sử s ≤ qk và |α− r/s| < |α− pk/qk|. Do 0 < s ≤ qk nên s|α− r/s| < qk|α− pk/qk|, hay |sα− r| < |qkα− pk|, và điều này mâu thuẫn với định lý 7.13.
Ví dụ 7.3.2. Phân số liên tục đơn giản của số π là π = [3; 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, ... ]. Thế thì các xấp xỉ hữu tỉ tốt nhất của số π là p0 q0 = 3, p1 q1 = 22 7 , p2 q2 = 333 106 , p3 q3 = 355 113 , p4 q4 = 103993 33102 , ....  Định lý 7.14. Nếu α là vô tỉ và r, s là các số nguyên với s > 0 sao cho |α− r/s| < 1/(2s2)| thì r/s là giản phân của phân số liên tục đơn giản biểu diễn α. Chứng minh. Giả sử r/s không là giản phân của phân số liên tục đơn giản biểu diễn α. Gọi k là số mà qk ≤ s < qk+1, theo định lý 7.13 thì |qkα− pk| ≤ |sα− r| = s|α− r/s| < 1/(2s). Suy ra |α− pk/qk| < 1/(2sqk). Nhưng do |spk − rqk| ≥ 1, nên 1 sqk ≤ |spk − rqk| sqk = ∣∣∣pk qk − r s ∣∣∣ ≤ ∣∣∣α− pk qk ∣∣∣+ ∣∣∣α− r s ∣∣∣ < 1 2sqk + 1 2s2 . Vậy 1 2sqk < 1 2s2 , kéo theo qk > s, và điều này vô lý với giả sử qk ≤ s < qk+1.
Phân số liên tục đơn giản vô hạn [a0; a1, a2, ... ] được gọi là tuần hoàn nếuu có các số nguyên dương N, k sao cho an = an + k với mọi n ≥ N. 7.3. PHÂN SỐ LIÊN TỤC VÔ HẠN 115 Định lý 7.15. Định lý Lagrange. Phân số liên tục đơn giản vô hạn của số α là tuần hoàn khi và chỉ khi α là số đại số bậc hai, nghĩa là α là nghiẹâm của đa thức bậc hai với hệ số nguyên và không là nghiẹâm của đa thức bậc thấp hơn 2,với hệ số nguyên. Định lý trên được chứng minh bởi các bổ đề sau đây. Bổ đềù 7.15.1. Nếu phân số liên tục đơn giản vô hạn của số α là tuần hoàn thì α là số đại số bậc hai. Chứng minh. Giả sử α = [a0; a1, a2, ..., aN−1aNaN+1...aN+k−1]. Ta ký hiệu β = [aN ; aN+1...aN+k−1]. Thế thì β = [aN ; aN+1...aN+k−1, β]. Suy ra β = βpk−1 + pk−2 βqk−1 + qk−2 , trong đó p−1k/qk−1, pk/qk là các giản phân của phân số liên tục [aN−1; aN , ..., aN+k−1]. Suy ra qk−1β2 + (qk−2 − pk−1)β − pk−2 = 0. Do β có biểu diễn phân số liên tục đơn giản vô hạn nên β là số vô tỉ và do đó không là nghiệm của đa thức hệ số nguyên có bậc nhỏ hơn 2.
Bổ đềù 7.15.2. Nếu α là số đại số bậc hai thì có các số nguyên P0, Q0 = 0 và d > 0 sao cho α = (P0 + √ d)/Q0 và Q0 | (d− P 20 ). Với k = 0, 1, 2, ... ta định nghĩa αk = (Pk + √ d)/Qk, ak = [αk], Pk+1 = akQk−Pk, Qk+1 = (d−P 2k+1)/Qk. Thế thì α = [a0; a1, a2, ... ]. 116 7. SỐ B- PHÂN. PHÂN SỐ LIÊN TỤC Chứng minh. Do α là số đại số bậc hai nên có các số nguyên a, b, c với c > 0 không là số chính phương để α = a + √ b c = a|c| +√bc2 c|c| . Lấy P0 = a |c| , d = bc2 , Q0 = c |c|. Hiển nhiên là P0, Q0 = 0 là các số nguyên và Q0 = c |c| | (d− P 20 ) = bc2 − a2c2 = c2(b− a2). Trước hết, bằng qui nạp chúng ta sẽ chứng tỏ rằng Pk, Qk là các số nguyên với Qk = 0 và Qk | (d − P 2k ). Từ giả thiết qui nạp ta suy ra Pk+1 = akQk − Pk là số nguyên. Ta cũng có Qk+1 = (d−P 2k+1)/Qk = (d−(akQk−Pk)2)/Qk = (d−P 2k )/Qk+(2akPk−a2kQk). Vì giả thiết qui nạp Qk | (d − P 2k ), ta suy ra Qk là số nguyên. Do d không là số chính phương nên Qk+1 = (d− P 2k+1)/Qk = 0. Ta lại có Qk = (d− P 2k+1)/Qk+1 là số nguyên nên Qk+1 | (d− P 2k+1). Để kết thúc việc chứng minh định lý ta chỉ cần chứng tỏ rằng αk+1 = 1/(αk − ak) hay cũng vậy (αk − ak) = 1/αk+1. Ta có αk − ak = Pk + √ d Qk − ak = √ d− (akQk − Pk) Qk = √ d− Pk+1 Qk = d− P 2k+1 Qk( √ d + Pk+1) = Qk+1 ( √ d + Pk+1) = 1/αk+1.
Bổ đềù 7.15.3. Nếu α là số đại số bậc hai thì phân số liên tục đơn giản của α là tuần hoàn. Chứng minh. Vì α = [a0; a1, ..., ak−1, αk] nên α = pk−1αk + pk−2 qk−1αk + qk−2 . 7.3. PHÂN SỐ LIÊN TỤC VÔ HẠN 117 Với số x = (a + √ b)/c ta ký hiệu x′ = (a−√b)/c. Thế thì α = pk−1α′k + pk−2 qk−1α′k + qk−2 . Từ phương trình trên ta suy ra α′k = −qk−2 qk−1 · α ′ − pk−2/qk−2 α′ − pk−1/qk−1 . Vì lim n→∞ pn/qn = α nên lim k→∞ α′ − pk−2/qk−2 α′ − pk−1/qk−1 = 1. Do đó có số nguyên M sao cho α′k 0 khi k ≥ 1 nên αk − α′k = Pk + √ d Qk − Pk − √ d Qk = 2 √ d Qk > 0, hay Qk > 0 khi k ≥ M. Vậy với k ≥ M thì 0 < Qk ≤ QkQk+1 = d− P 2k+1 ≤ d. Từ đây ta cũng có P 2k+1 < d, hay − √ d < Pk+1 < √ d với mọi k ≥M. Vậy có các số i < j thoả Pi = Pj và Qi = Qj. Từ định nghĩa của các αk ta suy ra αi = αj; cũng vậy ai = aj, ai+1 = aj+1, ai+2 = aj+2, ... . Thế thì α = [a0; a1, ..., ai−1, ai, ai+1, ..., aj−1 ].
118 7. SỐ B- PHÂN. PHÂN SỐ LIÊN TỤC 7.4 Vài ứng dụng của phân số liên tục Trước hết, nhờ phân số liên tục ta có thể tìm nghiệm riêng của phương trình Diophantus tuyếân tính ax + by = c. Nhớ lại là, phương trình trên có nghiệm khi và chỉ khi d = (a, b) | c. Trong trường hợp này, bằng cách chia cả hai vế cho d, nên ta có thể giả sử rằng (a, b) = 1. Giả sử (a, b) = 1 và a/b = [a0; a1, ..., an]. Vì a/b = pn/qn, và (a, b) = (pn/qn) = 1 nên a = pn, b = qn, trong đó pk/qk ký hiệu cho giản phân thứ k của phân số liên tục [a0; a1, ..., an]. Nhưng pnqn−1 − pn−1qn = (−1)n−1, nên aqn−1 − bpn−1 = (−1)n−1, kéo theo a(−1)n−1cqn−1 + b(−1)ncpn−1 = c. Hệ thức trên chứng tỏ x0 = (−1)n−1cqn−1, y0 = (−1)ncpn−1 là một nghiệm riêng của phương trình ax + by = c (Nhớ là có giả thiết (a, b) = 1). Vậy trong trương hợp (a, b) = 1 phương trình ax+ by = c có nghiệm tổng quát là x = x0 + bt, y = y0 − at, với t ∈ Z. Ví dụ 7.4.1. Giải phương trình 62x + 23y = 2. Vìù 62 = 23 · 2 + 16 23 = 16 · 1 + 7 16 = 7 · 2 + 2 7 = 2 · 3 + 1, 2 = 1 · 2 7.4. VÀI ỨNG DỤNG CỦA PHÂN SỐ LIÊN TỤC 119 nên ta có biểu diễn dạng phân số liên tục: 62/23 = [2; 1, 2, 3, 2]. Ta có p0 = a0 = 2, q0 = 1 p1 = a1a0 + 1 = 3, q1 = a1 = 1 p2 = a2p1 + p0 = 8, q2 = a2q1 + q0 = 3 p3 = a3p2 + p1 = 27, q3 = a3q2 + q1 = 10 Vì (62, 23) = 1 nên phương trình 62x + 23y = 2 có nghiệm riêng x0 = (−1)32q3 = −20, y0 = (−1)42p3 = 54. Vậy nghiệm tổng quát của phương trình 62x + 23y = 2 là x = −20 + 23t, y = 54− 62t, với t ∈ Z.  Cuối cùng chúng tôi đưa ra sự áp dụng phân số liên tục để phân tích số n ra thừa số. Nếu n là hợp số thì phương trình x2 − y2 = n có nghiệm nguyên x, y thoả x − y = 1. Phân tích n thành thừa số cũng có nghĩa là tìm các số nguyên x, y thoả x2 ≡ y2 (mod n), 0 < y < x < n, và x + y = n, vì khi đó (n, x− y) và (n, x + y) sẽ là các ước của n khác với 1 và n. Ví dụ 7.4.2. Vì 292 − 172 = 552 ≡ 0 (mod 69) nên (29− 17, 69) = (12, 69) và (29 + 17, 69) = (46, 69) là các ước khác 1 và 69 của 69. Sử dụng thuật toán Euclid ta có 3 và 23 là các ước không tầm thường của 69.  Phân số liên tục của √ n được sử dụng để tìm nghiệm của đồng dư x2 ≡ y2 (mod n) khi n không là số chính phương. Định lý 7.16. Giả sử n không là số chính phương. Đặt P0 = 0, Q0 = 1, αk = (Pk + √ n)/Qk, ak = [αk], Pk+1 = akQk − Pk, Qk+1 = (n − P 2k+1)/Qk với k = 0, 1, 2, ... . Khi đó nếu pk/qk là giản phân thứ k của √ n thì p2k − nq2k = (−1)k−1Qk+1. 120 7. SỐ B- PHÂN. PHÂN SỐ LIÊN TỤC Chứng minh. Ta đã biết √ n = [a0; a1, ..., ak, αk+1] và √ n = αk+1pk + pk−1 αk+1qk + qk−1 . Suy ra √ n = (Pk+1 + √ n)pk + Qk+1pk−1 (Pk+1 + √ n)qk + Qk+1qk−1 , hay nqk + (Pk+1qk +