Luận văn Về tính chia hết của các số fibonacci suy rộng

xác định bởi Fn = aFn−1 + bFn−2, n ≥ 2, với F0 = 0 và F1 = 1. Ngoài ra, Horadam [5] cũng đã định nghĩa một dãy Fibonacci suy rộng {Hn} bởi Hn = Hn−1 +Hn−2, n ≥ 3, với H1 = p và H2 = p+ q, 6 trong đó p và q là hai số nguyên bất kỳ. Ở đây, ta sẽ định nghĩa dãy Fibonacci suy rộng như sau: Định nghĩa 1.5. Dãy Fibonacci suy rộng {Fn} được định nghĩa bởi phương trình sai phân Fk = pFk−1 + qFk−2, k ≥ 2, (1.6) với điều kiện ban đầu F1 = a, F2 = b, trong đó p, q, a, b là các số nguyên dương. Với các giá trị khác nhau của p, q, a, b, dãy số xác định bởi Định nghĩa 1.5 cho ta rất nhiều dãy số khác nhau, trong đó có những dãy số mà ta đã biết đến: Với p = q = a = b = 1, ta thu được dãy Fibonacci thông thường; Với a = 2, p = q = b = 1, ta thu được dãy Lucas; ... 1.3 Một số tính chất của dãy Fibonacci suy rộng Trong mục này, chúng tôi sẽ trình bày các kết quả nghiên cứu của Panwar, Singh và Gupta [9] về hai trường hợp riêng của dãy Fibonacci suy rộng xác định bởi (1.6): • Dãy {Vk}k≥0 xác định bởi (1.6) với p = 1, q = a = b = 2, tức là: Vk = Vk−1 + 2Vk−2, k ≥ 2, với V0 = 2, V1 = 2; • Dãy {Uk}k≥0 xác định bởi (1.6) với p = 1, q = a = 2, b = 0, tức là: Uk = Uk−1 + 2Uk−2, k ≥ 2, với U0 = 2, U1 = 0. 7 Trước tiên, tương tự như các dãy số xác định bởi phương trình sai phân, hai dãy số này cũng có công thức Binet xác định số hạng tổng quát của chúng. Gọi R1 = 2 và R2 = −1 là hai nghiệm của phương trình đặc trưng x2 − x− 2 = 0. Khi đó, công thức Binet của hai dãy Fibonacci suy rộng {Un} và {Vn} được xác định bởi mệnh đề dưới đây. Mệnh đề 1.6 (Công thức Binet). Số hạng Fibonacci thứ k của dãy Fibonacci suy rộng Uk, Vk được xác định bởi (i) Vk = 2 Rk+11 −Rk+12 R1 −R2 ; (ii) Uk = 4 Rk−11 −Rk−12 R1 −R2 . Chứng minh. Chúng ta có thể sử dụng Định lý 1.2 để chứng minh công thức Binet hoặc chúng ta có thể chứng minh trực tiếp bằng phương pháp quy nạp. Ở đây, chúng tôi sẽ trình bày chứng minh theo quy nạp cho công thức Binet của dãy {Vn}. Chứng minh công thức Binet cho dãy {Un} hoàn toàn tương tự. Ta dễ kiểm tra được rằng, với n = 0, n = 1 định lý đúng. Giả sử định lý đúng với mọi r thỏa mãn 0 ≤ r ≤ s+ 1, tức là Vr = 2 Rr+11 −Rr+12 R1 −R2 , với mọi r thỏa mãn 0 ≤ r ≤ s. 8 Khi đó từ định nghĩa dãy Fibonacci suy rộng {Vn} ta có (lưu ý rằngR1 và R2 là hai nghiệm của phương trình x2 − x− 2 = 0) Vs+1 = Vs + 2Vs−1 = 2 Rr+21 −Rr+22 R1 −R2 . Như vậy công thức đúng với r = s + 1. Theo nguyên lý quy nạp toán học, công thức đúng với mọi r ≥ 0. Năm 1879, nhà thiên văn học người Pháp Jean-Diminique Cassini đã tìm ra một đẳng thức cho dãy số Fibonacci Fn−1Fn+1 − F 2n = (−1)n. Sau đó, công thức này đã được nhà toán học người Bỉ Eugene Charles Catalan tổng quát hóa thành F 2n − Fn−rFn+r = (−1)n−rF 2r . Định lý sau đây cho ta các đẳng thức tương tự đối với hai dãy số Fi- bonacci suy rộng {Un} và {Vn}. Định lý 1.7 (Đẳng thức Catalan). Với hai số tự nhiên r, n thỏa mãn r + 1 ≤ n ta có (i) Vn−r−1Vn+r−1 − V 2n−1 = (−1)n−r+12n−rV 2r−1; (ii) Un−r+1Un+r+1 − U2n+1 = (−1)n−r+12n−rU2r+1. Chứng minh. Ta sẽ chứng minh đẳng thức (i), đẳng thức (ii) được 9 chứng minh tương tự. Sử dụng công thức Binet của dãy {Vn}, ta có Vn−r−1Vn+r−1 − V 2n−1 = 2 ( Rn−r1 −Rn−r2 R1 −R2 ) 2 ( Rn+r1 −Rn+r2 R1 −R2 ) − 4 ( Rn1 −Rn2 R1 −R2 )2 = 4 9 [ −(R1R2)n ( R2 R1 )r − (R1R2)n ( R1 R2 )r + 2(R1R2) n ] = −4(−2)n 9 [( R2 R1 )r + ( R1 R2 )r − 2 ] = (−1)n+1−r2n+2 (−2)r ( Rr1 −Rr2 R1 −R2 )2 = (−1)n+1−r2n−r ( 2 Rr1 −Rr2 R1 −R2 )2 . Vậy Vn−r−1Vn+r−1 − V 2n−1 = (−1)n−r+12n−rV 2r−1. Trong đẳng thức Catalan, cho r = 1, ta thu được: Định lý 1.8 (Đẳng thức Cassini). Với số tự nhiên n ≥ 2, ta có (i) Vn−2Vn − V 2n−1 = (−1)n2n+1; (ii) Un+2Un − U2n+1 = (−1)n2n+3. Dãy số Fibonacci thỏa mãn đẳng thức sau đây, gọi là Đẳng thức d’Ocagne: FmFn+1 − Fm+1Fn = (−1)nFm−n. Định lý sau đây cho ta các đẳng thức tương tự đối với hai dãy Fibonacci suy rộng {Un} và {Vn}. Định lý 1.9 (Đẳng thức d’Ocagne). Với hai số nguyên dương n và m bất kỳ, ta có (i) Um+1Un − UmUn+1 =  8 3 (Rn1 +R m 1 ), n chẵn,m lẻ, −8 3 (Rn1 +R m 1 ), n lẻ,m chẵn; 10 (ii) VmVn−1 − Vm−1Vn =  −4 3 (Rn1 +R m 1 ), n chẵn,m lẻ, 4 3 (Rn1 +R m 1 ), n lẻ,m chẵn. Chứng minh. Ta sẽ chứng minh đẳng thức (i), đẳng thức (ii) được chứng minh hoàn toàn tương tự. Ta có Um+1Un − UmUn+1 = 16 9 [ (Rm1 −Rm2 )(Rn−11 −Rn−12 )− (Rm−11 −Rm−12 )(Rn1 −Rn2 ) ] = 16 9 [ Rm−11 R n 2 −Rm1 Rn−12 +Rm−12 Rn1 −Rm2 Rn−11 ] = 16 9 ( 1 R1 − 1R2 ) (Rm1 R n 2 −Rn1Rm2 ) = 8 3 (Rm1 R n 2 −Rn1Rm2 ). Từ đây suy ra Um+1Un − UmUn+1 =  8 3 (Rn1 +R m 1 ), n chẵn,m lẻ, −8 3 (Rn1 +R m 1 ), n lẻ,m chẵn. Định lý sau đây cho ta thấy rằng giới hạn của thương của hai số hạng liên tiếp của hai hãy Fibonacci suy rộng bằng nghiệm dương của phương trình đặc trưng tương ứng với phương trình sai phân xác định hai dãy này. Định lý 1.10. Ta có 1. lim k→∞ ( Vk−1 Vk−2 ) = R1; 2. lim k→∞ ( Uk+1 Uk ) = R1. Chứng minh. 1. Sử dụng công thức Binet ta có lim k→∞ ( Vk−1 Vk−2 ) = lim k→∞ Rk1 −Rk2 Rk−11 −Rk−12 = lim k→∞ 1− ( R2 R1 )k 1 R1 − ( R2 R1 )k 1 R2 11 Ta có lim k→∞ ( R2 R1 )k = 0 vì |R2| < R1. Từ đó, ta thu được điều phải chứng minh. Chứng minh 2. Tương tự như chứng minh 1. Định lý sau đây cho ta đẳng thức khác của hai dãy Fibonacci suy rộng {Un} và {Vn}. Định lý 1.11. Với dãy Fibonacci suy rộng {Vn} ta có 1. V 22k + V 2 2k+2 = 8 9 [ 34(16)k + 10(4)k + 1 ] 2. V 22k − V 22k+2 = −169 [ 12(16)k + (4)k ] Chứng minh. 1. Sử dụng công thức Binet, ta có V 22k+V 2 2k+2 = 4 9 [ R4k+21 +R 4k+2 2 − 2(R1R2)2k+1 +R4k+61 +R4k+62 − 2(R1R2)2k+3 ] = 4 9 [ R4k+21 ( 1 +R4k1 ) +R4k+22 ( 1 +R4k2 )− 2(R1R2)2k+1 {1 + (R1R2)2}] = 4 9 [ 17R4k+21 + 2R 4k+2 2 − 10(R1R2)2k+1 ] = 4 9 [ 68R4k1 + 2R 4k 2 + 20(R1R2) 2k ] = 4 9 [ 68(16) k + 2 + 20(4) k ] = 8 9 [ 34(16) k + 1 + 10(4) k ] . Chứng minh 2. Tương tự như chứng minh 1. Hoàn toàn tương tự, ta có các đẳng thức sau đối với dãy Fibonacci suy rộng {Un}. 12 Định lý 1.12. Với dãy {Uk}k≥0 ta có 1. U22k + U 2 2k+2 = 16 9 [ 17 4 (16) k + 5(4)k ] ; 2. U22k − U22k+2 = −489 [ 5(4)2k−1 + (4)k ] . 13 Chương 2 Tính chia hết của các số Fibonacci suy rộng Trong chương này, chúng tôi tập trung trình bày lại một số kết quả về tính chia hết của một số dãy Fibonacci suy rộng. Cụ thể, chúng tôi trình bày lại một số kết quả của Hoggatt và Long [4]; các kết quả của Aoki và Sakai [2, 3]. 2.1 Kết quả của Hoggatt và Long Trong mục này, chúng tôi trình bày các kết quả của Hoggatt và Long [4] về một số tính chất liên quan đến tính chia hết của dãy Fibonacci suy rộng {un} xác định bởi un+2 = pun+1 + qun, với u0 = 0 và u1 = 1, trong đó, p và q là hai số nguyên dương. Trước tiên, ta thấy rằng phương trình đặc trưng tương ứng x2 − px− q = 0 có hai nghiệm α = p+ √ p2 + 4q 2 và β = p− √ p2 + 4q 2 . 14 Do đó, công thức Binet cho dãy {un} là un = αn − βn α− β , n ≥ 0. Sử dụng công thức Binet này, ta chứng minh được đẳng thức sau đây: Định lý 2.1. Vớim ≥ 0 và n ≥ 0, ta có um+n+1 = um+1un+1 + qumun. Ta sẽ chứng minh rằng, với mọi n ≥ 0, un và un+1 là nguyên tố cùng nhau. Trước tiên, ta cần bổ đề sau đây: Bổ đề 2.2. Với mọi n > 0, ta có (q, un) = 1. Chứng minh. Ta thấy điều khẳng định đúng với n = 1 khi đó u1 = 1. Giả sử rằng bổ đề đúng với k bất kì, k ≥ 1. Khi đó ta có uk+1 = puk + quk−1. Khẳng định này đúng với n = k + 1, và vì thế khẳng định đúng với mọi n ≥ 1. Định lý 2.3. Với n ≥ 0, ta có (un, un+1) = 1. Chứng minh. Định lý đúng với n = 0 và n = 1. Khi đó u0 = 0, u1 = 1, và u2 = p. Giả sử rằng định lý đúng với n = k − 1, trong đó k là số nguyên cố định, k ≥ 2 và cho d(p, q) = (uk, uk+1). Khi đó uk+1 = puk + quk−1. 15 Điều này có nghĩa rằng d(p, q)|uk−1q. Nhưng theo Bổ đề 2.2 ta có (d(p, q), q) = 1, và do đó d(p, q)|uk−1. Nhưng khi d(p, q)|1 thì (uk−1, uk) = 1, và khi đó định lý đúng với mọi n ≥ 0. Điều phải chứng minh. Bổ đề 2.4. Với n ≥ 0, ta có un = [(n−1)/2]∑ i=0 ( n− i− 1 i ) pn−2i−1qi. Chứng minh. Ta quy ước tổng rỗng bằng không nên kết quả đúng với n= 0. Với n = 1, tổng chỉ chứa một số hạng 0 0  p0q0 = 1 = u1. Giả sử đẳng thức đúng với n = k−1 và n = k, với k cố định và k ≥ 1. Khi đó uk+1 = puk + quk−1 = [(k−1)/2]∑ i=0  k − i− 1 i pk−2iqi+ [(k−2)/2]∑ i=0  k − i− 2 i pk−2i−2qi+1 = [(k−1)/2]∑ i=0  k − i− 1 i pk−2iqi + [k/2]∑ i=0  k − i− 2 i− 1 pk−2iqi = [k/2]∑ i=0  k − i i pk−2iqi. Do đó kết quả đúng với n = k + 1, và do đó cũng đúng với mọi n ≥ 0. Điều phải chứng minh. 16 Định lý 2.5. Với n ≥ m ≥ 2, ta có um | un khi và chỉ khim | n. Chứng minh. Rõ ràng um|um. Giả sử rằng um|ukm với k ≥ 1 cố định. Khi đó theo Định lý 2.1 u(k+1)m = ukm+m = ukmum+1 + qukm−1um. Nhưng từ giả thiết um|ukm thì um|u(k+1)m. Do đó, um|un nếum|n. Giả sử rằng m ≥ 2 và um|un. Nếu m - n thì tồn tại số nguyên t và r với 0 < r < m, sao cho n = mt+ r. Theo Định lý 2.1, chúng ta có un = umt+r = umt+1ur + qumtur−1. Theo chứng minh trên, nếu um|umt thìum|umt+1ur. Nhưng theo Định lý 2.3 nếu (umt, umt+1) = 1 thì um|ur điều này mâu thuẫn khi bậc của ur nhỏ hơn um trong p. Do đó, r = 0 và m|n. Điều phải chứng minh. Định lý 2.6. Vớim ≥ 0 và n ≥ 0, ta có (um, un) = u(m,n). Chứng minh. Cho d = d(p, q) = (um, un). Theo Định lý 2.5 suy ra u(m,n)|d. Khi đó tồn tại số nguyên r và s với r > 0 và s < 0 sao cho (m,n) = rm+ sn. Do đó, theo Định lý 2.1 urm = u(m,n)+(−s)n 17 = u(m,n)u−sn+1 + qu(m,n)−1u−sn. Nhưng khi d|u−sn và d|urm theo Định lý 2.5 ta cũng có d|u(m,n)u−sn+1. Nhưng, theo Định lý 2.3 ta có (d, u−sn+1) = 1. Do đó d|u(m,n), suy ra d = u(m,n). Định lý được chứng minh. 2.2 Kết quả của Aoki và Sakai Trong mục này, chúng tôi trình bày lại các kết quả của Aoki và Sakai [2, 3] về tính chia hết của dãy số Fibonacci suy rộng {Gn} xác định bởi G1, G2 ∈ Z và Gn+2 = Gn+1 +Gn với mọi n ≥ 1. (2.1) Chúng ta biết rằng nếu p là một số nguyên tố thì p sẽ là ước của ít nhất một số Fibonacci Fn nào đó. Cố định một số nguyên tố p và đặt d(p) = min{n ∈ Z | Fn ≡ 0 mod p}. Khi đó ta có d(p) ≤ p+ 1 (xem [7]) Fn ≡ 0 mod p nếu và chỉ nếu n ≡ 0 mod d(p). Ngoài ra, chúng ta có kết quả sau: Bổ đề 2.7 ([7, Theorem 34.8]). Cho p là một số nguyên tố. Khi đó, (1) nếu p ≡ ±1( mod 5) thì Fp−1 ≡ 0 mod p; (2) nếu p ≡ ±2( mod 5) thì Fp+1 ≡ 0 mod p. 18 Với số nguyên G không chia hết cho p, ta kí hiệu nhịch đảo của G modulo p bởi G−1(∈ Z), tức là, GG−1 ≡ 1 mod p. Trên tập các dãy Fibonacci suy rộng xác định bởi (2.1), ta định nghĩa một quan hệ hai ngôi sau đây: Định nghĩa 2.8. Cho {Gn}và {G′n} là hai dãy Fibonacci suy rộng thỏa mãn p không là ước của G1, G2 và p không là ước của G ′ 1, G ′ 2. Nếu G2G1 −1 ≡ G′2G′1 −1 mod p thì ta viết {Gn} ∼ {G′n}. Dễ dàng thấy rằng quan hệ ∼ là một quan hệ tương đương trên tập các dãy Fibonacci suy rộng xác định bởi (2.1). Ta kí hiệu tập thương của quan hệ tương đương này bởi Xp = {Dãy Fibonacci suy rộng {Gn} thỏa mãn p - G1, G2}/ ∼ . Theo định nghĩa của quan hệ ∼, mỗi lớp {Gn} ∈ Xp chứa vô hạn các dãy Fibonacci suy rộng. Số lớp tương đương {Gn} của Xp là |Xp| = |F×p | = p− 1. Kí hiệu Yp là tập con của Xp xác định bởi Yp = { {Gn} ∈ Xp|p - Gn,∀n ∈ N } . Bổ đề sau đây cho ta thấy điều kiện "p không là ước củaGn với mọi n ∈ N" không phụ thuộc vào việc chọn đại diện {Gn} của lớp tương đương nên định nghĩa của tập con Yp hoàn toàn có nghĩa. Bổ đề 2.9. Giả sử p không là ước của G1, G2, p không là ước của G ′ 1, G ′ 2 và {Gn} ∼ {G′n}. Khi đó chúng ta có p không là ước của Gn khi và chỉ khi p không là ước của G ′ n với mọi n ∈ N. 19 Chứng minh. Cho a là số nguyên tố thỏa mãn a ≡ G2G−11 ≡ G ′ 2G ′ 1 −1 (mod p) và 1 ≤ a ≤ p − 1, và {An} là dãy Fibonacci suy rộng định nghĩa bởi A1 = 1 và A2 = a. Khi đó chúng ta có Gn ≡ AnG1 và G ′ n ≡ AnG′1 (mod p) với mọi n ∈ N. Ngược lại nếu p không chia hết cho G1 và G ′ 1 chúng ta có p|Gn khi và chỉ khi p|G′n. Với mọi i nguyên dương thỏa mãn i 6≡ 0 mod d(p), gọi gi(0 ≤ gi ≤ p− 1) là số nguyên thỏa mãn gi ≡ Fi+1F−1i mod p. Bổ đề 2.10. Cho i và j là các số nguyên dương thỏa mãn i, j 6≡ 0 mod d(p). Khi đó ta có gi = gj khi và chỉ khi i ≡ j mod d(p). Chứng minh. Chúng ta xét 2 dãy con của Fn mod p: Fi, Fi+1 ≡ giFi, Fi+2 ≡ (1 + gi)Fi, Fi+3 ≡ (1 + 2gi)Fi, ..., Fj, Fj+1 ≡ gjFj, Fj+2 ≡ (1 + gj)Fj, Fj+3 ≡ (1 + 2gj)Fj, ..., Giả sử gi = gj và cho k là số nguyên dương. Bởi vì p không chia hết Fi và Fj, chúng ta có Fi+k ≡ 0 (mod p) khi và chỉ khi Fj+k ≡ 0(mod p). Chúng ta kết luận rằng i+ k ≡ j + k (mod d(p)) với k ∈ N do đó i ≡ j (mod d(p)). Ngược lại, chúng ta giả sử i ≡ j (mod d(p)). Cho {In} và {Jn} là các dãy Fibonacci suy rộng thỏa mãn I1 = J1 = 1 và I2 = gi, J2 = gj. Chúng ta kí hiệu hai dãy con ở trên mod p bởi Fi, Fi+1 ≡ I2Fi, Fi+2 ≡ I3Fi, Fi+3 ≡ I4Fi, ..., Fj, Fj+1 ≡ J2Fj, Fj+2 ≡ J3Fj, Fj+3 ≡ J4Fj, ... 20 Theo giả thiết i ≡ j (mod d(p)), với bất kì một số nguyên dương k nào chúng ta có i + k ≡ 0(mod d(p)) khi và chỉ khi j + k ≡ 0(mod d(p)). Do đó, chúng ta có Fi+k ≡ 0 (mod p) khi và chỉ khi Fj+k ≡ 0(mod d(p)). Vì p không chia hết Fi và Fj nên Ik+1 ≡ 0 khi và chỉ khi Jk+1 ≡ 0(mod p). Theo công thức Ik+1 = Fk−1I1 + FkI2 = Fk−1 + Fkgi và Jk+1 = Fk−1J1 + FkJ2 = Fk−1 + Fkgj, chúng ta có Fkgi ≡ Fkgj (mod p). Vì k 6≡ 0 (mod d(p)) bởi i, j 6≡ 0(mod d(p)), chúng ta có gi ≡ gj(mod p). Hơn nữa do 0 ≤ gi, gj ≤ p− 1 nên gi = gj. Nếu p ≡ ±2 mod 5 thì theo Bổ đề 2.7 ta có d(p) ≤ p + 1. Bổ đề sau đây cho ta điều kiện cần để d(p) = p+ 1. Bổ đề 2.11. Cho p là một số nguyên tố lẻ. Nếu d(p) = p + 1, khi đó chúng ta có p ≡ 3 mod 4. Chứng minh. Áp dụng tính chất Fn+m = FmFn+1+Fm−1Fn với (n,m) = ( p−1 2 , p+1 2 ) và (n,m) = ( p+1 2 , p+3 2 ) , chúng ta nhận được F 2p+1 2 + F 2p−1 2 = Fp và F 2p+3 2 +F 2p+1 2 = Fp+2. Theo giả thiết d(p) = p+1, Bổ đề 2.7 và d(p) = 5, chúng ta có p ≡ ±2 mod 5. Mặt khác chúng ta có Fp ≡ −1 mod p và Fp+2 ≡ −1 mod p vì Fp+1 ≡ 0 mod p. Hơn nữa, từ −1 ≡ F 2p+3 2 + F 2p+1 2 mod p = ( Fp+1 2 + Fp−1 2 )2 + F 2p+1 2 21 ≡ 2Fp+1 2 Fp−1 2 − 1 + F 2p+1 2 mod p, suy raFp+1 2 ( 2Fp−1 2 − Fp+1 2 ) ≡ 0 mod p do đóFp+1 2 ≡ −2Fp−1 2 mod p vì d(p) = p + 1. Chúng ta nhận được −1 ≡ F 2p+1 2 + F 2p−1 2 ≡ 5F 2p−1 2 mod p. Nếu chúng ta giả sử p ≡ 1 mod 4 thì chúng ta có( 5F 2p−1 2 p ) = ( 5 p ) = (p 5 ) = (±2 5 ) = −1 và (−1 p ) = 1. Điều này mâu thuẫn với 5F 2p−1 2 ≡ −1 (mod p). Do đó ta có được p ≡ 3 (mod 4). Mệnh đề 2.12. Giả sử p - G1, G2. Với mọi số nguyên dương n thỏa mãn n 6≡ 2 mod d(p). Chúng ta có p|Gn khi và chỉ khi −G1G−12 ≡ gn−2 (mod p). Chứng minh. Chứng minh Bổ đề trên được suy ra trực tiếp từ công thức Gn = Fn−2G1 + Fn−1G2. Mệnh đề 2.13. Giả sử p - G1, G2. Chúng ta có p|Gn với n ∈ N khi và chỉ khi −G1G−12 ≡ gi (mod p) với 1 ≤ i ≤ d(p)− 2. Chứng minh. Nếu n ≡ 2 (mod d(p)), khi đó ta có Gn = Fn−2G1 + Fn−1G2 ≡ Fn−1G2 6≡ 0 (mod p). Hơn thế nữa nếu i = d(p) − 1 thì −G1G−12 6≡ gi(mod p) do chúng ta đã giả thiết p - G1 và gd(p)−1 ≡ Fd(p)F −1 d(p)−1 ≡ 0 (mod p). Vì vậy ta chỉ cần chứng minh rằng p|Gn với n ∈ N thỏa mãn n 6≡ 2(mod d(p)) khi và chỉ khi −G1G−12 ≡ gi(mod p) với i thỏa mãn 1 ≤ i ≤ d(p)− 1. Điều này được suy ra từ Mệnh đề 2.12 và Bổ đề 2.10. 22 Kí hiệu dãy Fibonacci suy rộng {Gn} sao cho G1 = a, và G2 = b, (a, b ∈ Z) bởi {G(a, b)}. Ví dụ {Fn} = {G(1, 1)} và {Ln} = {G(1, 3)}. Chúng ta có thể viết Xp = { {G(1, k)}|1 ≤ k ≤ p− 1 } . Định lý 2.14. Với các kí hiệu như trên, ta có (1) Yp = Xp − { {G(1, gi)}|1 ≤ i ≤ d(p)− 2 } ; (2) |Yp| = p+ 1− d(p). Chứng minh. (1) Vì dãy số Fibonacci thỏa mãn Fn+m = FmFn+1 + Fm−1Fn, chúng ta có 0 ≡ Fd(p) = Fi+(d(p)−i) = Fd(p)−iFi+1+Fd(p)−i−1Fi (mod p) vớii bất kì,(1 ≤ i ≤ d(p) − 2). Vì thế gi ≡ −g−1d(p)−i−1 (mod p). Theo Bổ đề 2.10 và Mệnh đề 2.13, chúng ta có Yp = Xp − { {Gn} ∈ Xp|p|Gn, n ∈ N } = Xp − { {G (1, k)}|1 ≤ k ≤ p− 1,−k−1 ≡ gi(modp); 1 ≤ i ≤ d(p)− 2 } = Xp − { {G (1, k)}|1 ≤ k ≤ p− 1,−k−1 ≡ gd(p)−i−1(modp); 1 ≤ i ≤ d(p)− 2 } = Xp − { {G (1, k)}|1 ≤ k ≤ p− 1, k ≡ −g−1d(p)−i−1(modp); 1 ≤ i ≤ d(p)− 2 } = Xp − { {G (1, gi)}|1 ≤ i ≤ d(p)− 2 } . (2) Theo Bổ đề 2.10, ta có gi 6= gj nếu 1 ≤ i, j ≤ d(p)− 2 và i 6= j. Từ đó suy ra |Yp| = |Xp| − (d(p) − 2) = (p − 1) − (d(p) − 2) = p+ 1− d(p). Áp dụng Định lý 2.14, Bổ đề 2.7 với d(5) = 5, ta có hệ quả sau. Hệ quả 2.15. (1) |Y5| = 1. (2) Nếu p ≡ ±1 mod 5 thì chúng ta có vô hạn dãy Fibonacci suy rộng {Gn} thỏa mãn p - Gn với mọi n ∈ N. 23 (3) Nếu p ≡ ±2 mod 5 và d(p) = p + 1, thì với mọi dãy Fibonacci suy rộng {Gn}, ta có p|Gn với mọi n ∈ N. Định nghĩa 2.16. Cho (Gn) và (G ′ n) là hai dãy Fibonacci suy rộng xác định bởi (2.1). Chúng ta viết (Gn) ∼∗ (G′n) nếu có hai số nguyên m và n thỏa mãn Gm+1G ′ n ≡ G′n+1Gm (mod p). Từ định nghĩa của hai quan hệ ∼ và ∼∗, ta suy ra: Bổ đề 2.17. Nếu (Gn) ∼ (G′n) thì ta có (Gn) ∼∗ (G′n). Chú ý rằng nếu dãy (Gn) thỏa mãn p | G1 và p | G2 thì chúng ta có (Gn) ∼ (G′n) và (Gn) ∼∗ (G′n) với mọi dãy Fibonacci suy rộng (G′n) xác định bởi (2.1). Ở trên ta thấy ∼ là một quan hệ tương đương trên tập các dãy Fibonacci suy rộng (Gn) xác định bởi (2.1) thỏa mãn p - G1 hoặc p - G2. Chúng ta sẽ chỉ ra rằng quan hệ ∼∗ cũng là một quan hệ tương đương trên tập hợp này. Trước tiên, từ công thức truy hồi Gn = Gn−1+Gn−2 ta suy ra ngay bổ đề sau đây: Bổ đề 2.18. Cho (Gn) là một dãy Fibonacci suy rộng xác định bởi (2.1) thỏa mãn p - G1 hoặc p - G2. Nếu p|Gn thì p - Gn−1 và p - Gn+1. Bổ đề 2.19. Cho (Gn) và (G ′ n) là hai dãy Fibonacci suy rộng xác định bởi (2.1). Nếu Gm+1G ′ n ≡ G′n+1Gm( mod p) thì Gm+2G′n+1 ≡ G ′ n+2Gm+1( mod p). 24 Chứng minh. Gm+2G ′ n+1 = (Gm+1 +Gm)G ′ n+1 = Gm+1G ′ n+1 +GmG ′ n+1 ≡ Gm+1G′n+1 +Gm+1G ′ n = Gm+1(G ′ n+1 +G ′ n) = Gm+1G ′ n+2. Bổ đề 2.20. Quan hệ ∼∗ là một quan hệ tương đương trên tập các dãy Fibonacci suy rộng (Gn) xác định bởi (2.1) thỏa mãn p - G1 hoặc p - G2. Chứng minh. Dễ thấy quan hệ ∼∗ có tính chất phản xạ và đối xứng. Chúng ta chỉ cần chứng minh tính chất bắc cầu: nếu (Gn) ∼∗ (G′n) và (G ′ n) ∼∗ (G′′n) thì (Gn) ∼∗ (G′′n). Theo giả thiết tồn tại các số nguyên m,n, k, l thỏa mãn Gm+1G ′ n ≡ G ′ n+1Gm mod p và G ′ k+1G ′′ l ≡ G ′′ l+1G ′ k mod p. Đặt t = max(n, k). Theo Bổ đề 2.19, ta suy ra các số nguyên m và l thỏa mãn Gm+1G ′ t ≡ G ′ t+1Gm mod p và G ′ t+1G ′′ l ≡ G ′′ l+1G ′ t mod p. (2.2) Giả sử nếu p|G′t thì ta có p - G′t+1 theo Bổ đề 2.18. Từ (2.2) ta có p|Gm và p|G′′l . Vì vậy chúng ta có (Gn) ∼∗ (G ′′ n)vì Gm+1G ′′ l ≡ 0 ≡ 25 G ′′ l+1Gm mod p. Nếu ta giả thiết p|G ′ t+1 thì bằng cách lập luận tương tự ta có (Gn) ∼∗ (G′′n). Tiếp theo chúng ta giả sử p - G′t và p - G′t+1. Khi đó chúng ta có được p - Gm và p - G ′′ l từ (2.2). Do đó chúng ta có Gm+1G−1m ≡ G′t+1G ′−1 t ≡ G′′l+1Gn−1l mod p và do đó Gm+1G ′′ l ≡ G ′′ l+1Gm mod p. Đồng dư này có nghĩa (Gn) ∼∗ (G ′′ n). Bổ đề 2.21. Giả sử (Gn), (G ′ n) là hai dãy Fibonacci suy rộng xác định bởi (2.1) thỏa mãn p - G1 hoặc p - G2. Nếu (Gn) ∼∗ (G′n) và p - Gn với mọi n ∈ Z thì chúng ta có p - G′n với mọi n ∈ Z. Chứng minh. Giả sử rằng tồn tại hai số nguyênm,n thỏa mãnGm+1G ′ n ≡ G′n+1Gm (mod p). Giả sử rằng tồn tai số nguyên l sao cho p|G′l. Do tính tuần hoàn của (G ′ n mod p), chúng ta có thể giả sử l ≥ n. Sử dụng Bổ đề 2.19, ta suy ra tồn tại số nguyên k sao cho Gk+1G ′ l ≡ G ′ l+1Gk (mod p).Vì p chia hết G ′ l và không chia hết G ′ l+1 nên suy ra p|Gk. Mẫu thuẫn với giả thiết. Bổ đề 2.22. Cho (Gn) là một dãy Fibonacci suy rộng xác định bởi (2.1). Khi đó tồn tại một số nguyên n thỏa mãn p|Gn nếu và chỉ nếu (Gn) ∼∗ (Fn). Chứng minh. Đầu tiên, chúng ta giả sử tồn tại một số nguyên n thỏa mãn p|Gn. Chúng ta có (Gn) ∼∗ (Fn) vì F1Gn ≡ 0 ≡ Gn+1F0 (mod p). (Chú ý rằng F0 = 0). Tiếp theo, chúng ta giả sử (Gn) ∼∗ (Fn). Khi đó phải tồn tại hai số nguyên m và n thỏa mãn Gm+1Fn ≡ Fn+1Gm (mod p). Mặt khác, vì 26 F0 = 0 và do tính tuần hoàn của (Fn mod p) nên tồn tại số nguyên l thỏa mãn p|Fl với l ≥ n. Sử dụng Bổ đề 2.19 ta suy ra có số nguyên k sao cho Gk+1Fl ≡ Fl+1Gk (mod p). Theo Bổ đề 2.18 thì p - Fl+1 nên ta có p|Gk. Bây giờ chúng ta xét tập thương trên quan hệ tương đương ∼∗: X∗p = {(Gn) | p - G1 hoặc p - G2}/ ∼∗ . Đặt Y ∗p = {(Gn) ∈ X∗p | p - Gn với mọi n ∈ Z}. Bổ đề 2.23. (1) X∗p = Y ∗p ∪ {(Fn)}. (2) Với mọi lớp tương đương (Gn) củaX∗p , ta có thể chọn phần tự đại diện (Gn) thỏa mãn p - G1, G2. (3) Cho (Gn) là một lớp tương đương của Y ∗p . Với mọi dãy (G ′ n) ∈ (Gn), ta có p - G′1, G′2. Chứng minh. Khẳng định (1) được suy ra từ Bổ đề 2.22. Chúng ta sẽ đi chứng minh khẳng định (2). Giả sử p|G1 hoặc p|G2, khi đó theo Bổ đề 2.22 ta có (Gn) ∼∗ (Fn). Do đó ta có (Gn) = (Fn) và F1 = F2 = 1. Khẳng định (3) được suy ra từ Bổ đề 2.21. Bổ đề 2.24. Cho p(6= 2, 5) là một số nguyên tố. (1) Nếu p ≡ ±1( mod 5), khi đó X2 − X − 1 = 0 có hai nghiệm phân biệt trong Fp. 27 (2) Nếu p ≡ ±2( mod 5), khi đó X2 −X − 1 = 0 vô nghiệm trong Fp. Chứng minh. Nghiệm củaX2−X − 1 = 0 trong Fp (bao đóng đại số của Fp) làX = 2−1(1± √ 5). Do giả thiết p 6= 2, 5 nên các nghiệm này khác nhau. Chúng ta có 2−1(1±√5) ∈ Fp khi và chỉ khi √ 5 ∈ Fp.Hơn thế nữa điều này tương đương với ( 5 p ) = ( p 5 ) = 1, tức là p ≡ ±1(mod 5). Định nghĩa 2.25. (1) Với bất kì số nguyên n thỏa mãn n 6≡ 0 mod d(p), chúng ta định nghĩa số nguyên fn(0 ≤ fn ≤ p − 1) thỏa mãn fn ≡ Fn+1F−1n mod p. (2) Cho (Gn) là dãy Fibonacci suy rộng xác định bởi (2.1) thỏa mãn p - Gn với mọi n ∈ Z. Chúng ta có thể định nghĩa số nguyên gn(1 ≤ gn ≤ p− 1) sao cho gn ≡ Gn+1G−1n mod p. Bằng phương pháp quy nạp, ta có thể dễ dàng chứng minh được hai bổ đề dưới đây: Bổ đề 2.26. Với mọi n,m ∈ Z, chúng ta có Gn = Fn−mGm+1 + Fn−m−1Gm. Bổ đề 2.27. Với mọi n ∈ Z, chúng ta có G2n+1 −GnGn+1 −G2n = −(G2n −Gn−1Gn −G2n−1). Để đơn giản, chúng ta đưa ra một kí hiệu mới. Nếu (Gn) là một dãy 28 Fibonacci suy rộng xác định bởi (2.1) thỏa mãn G1 = a và G2 = b thì chúng ta sẽ viết (Gn) = (G(a,b)). Định lý 2.28. Giả sử rằng (Gn) = (G(a,b)) thỏa mãn p - Gn với mọi n ∈ Z. Giả sử thêm rằng a và b thỏa mãn b2 − ab − a2 6≡ 0 (mod p). Với mọi số nguyên n vàm, chúng ta có gn = gm khi và chỉ khi n ≡ m mod d(p). Chứng minh. Đầu tiên theo định nghĩa của gn và gm, chúng ta có gn = gm khi và chỉ khi GmGn+1 ≡ Gm+1Gn mod p. Vì Gn+1 = Fn−m+1Gm+1 + Fn−mGm và Gn = Fn−mGm+1 + Fn−m−1Gm theo Bổ đề 2.26, Chúng ta có gn ≡ gm khi và chỉ khi G2m+1Fn−m−GmGm+1(Fn−m+1−Fn−m−1)−G2mF 2n−m ≡ 0 (mod p). (2.3) Theo Bổ đề 2.27,với vế trái của (2.3), chúng ta có G2m+1Fn−m −GmGm+1(Fn−m+1 − Fn−m−1)−G2mFn−m ≡ G2m+1Fn−m −GmGm+1Fn−m −G2mFn−m ≡ (G2m+1 −GmGm+1 −G2m)Fn−m ≡ (−1)m−1(G22 −G1G2 −G21)Fn−m ≡ (−1)m−1(b2 − ab− a2)Fn−m mod p. Theo giả thiết b2 − ab− a2 6≡ 0 mod p, ta suy ra gn = gm khi và chỉ khi n ≡ m mod d(p). 29 Định nghĩa 2.29. Giả sử (Gn = (G(a, b))) thỏa mãn p - Gn với mọi n ∈ Z. Chúng ta định nghĩa chu kì thứ hai của (Gn) bởi chu kì của (gn). Hệ quả 2.30. Giả sử rằng (Gn) = (G(a, b)) thỏa mãn p - Gn với mọi n ∈ Z. (1) Nếu b2 − ab − a2 ≡ 0 mod p, khi đó chu kì thứ hai của (Gn) bằng 1. (2) Nếu b2 − ab − a2 6≡ 0 mod p, khi đó chu kì thứ hai của (Gn) bằng d(p). Chứng minh. Khẳng định (2) sau đây từ Định lý 2.28. Chúng ta sẽ chứng minh (1) bằng cách chỉ ra rằng gn = g1 ≡ ba−1 mod p với mọi n ∈ Z. Do tính tuần hoàn của (Gn)mod p ta chỉ cần xét n ∈ N. Chúng ta sử dụng phương pháp quy nạp. Với n = 1, khẳng định đúng. Chúng ta giả sử rằng khẳng định đúng với bất kì số tự nhiên nhỏ hơn n + 1. Khi đó chúng ta có gn+1 ≡ Gn+2G−1n+1 ≡ (Gn+1 +Gn)(Gn +Gn−1)−1 ≡ (Gn+1G−1n + 1)(1 +Gn−1G−1n )−1 ≡ (gn + 1)(1 + g−1n−1)−1 ≡ (ba−1 + 1)(1 + b−1a)−1 ≡ (ba−1 + 1)× {b−1a(ba−1 + 1)}−1 30 ≡ ba−1 ≡ g1 mod p. Mặt khác 1 ≤ g1, gn+1 ≤ p− 1, chúng ta có gn+1 = g1. Bổ đề 2.31. Giả sử rằng (Gn) và (G ′ n) thỏa mãn p - Gn, G ′ n với mọi n ∈ Z. Cho υ là chu kì thứ hai của G′n. Khi đó ta có (Gn) ∼∗ (G′n) khi và chỉ khi tồn tại số nguyên n với (1 ≤ n ≤ υ) sao cho g′n = g1(≡ G2G −1 1 mod p). Chứng minh. Đầu tiên, chúng ta giả sử g ′ n = g1 với một số nguyên n(1 ≤ n ≤ υ). Khi đó chúng ta có đượcG′n−1G′n −1 ≡ G2G−11 mod p và do đó (Gn) ∼∗ (G′n). Tiếp theo, chúng ta giả sử (Gn) ∼∗ (G′n). Khi đó phải tồn tại hai số nguyên m và n sao cho Gm+1G ′ n ≡ G′n+1Gm mod p. Theo Bổ đề 2.19, tồn tại một số nguyên n sao cho G2G ′ n ≡ G′n+1G1 mod p. Vì thế chúng ta có được g ′ n ≡ g1 mod p. Chúng ta có g1 = g′n do 1 ≤ g1 ≤ p − 1 và 1 ≤ gn ≤ p − 1. Hơn nữa, chúng ta có thể chọn một số nguyên n như vậy thỏa mãn 1 ≤ n ≤ υ bởi vì chu kì của (g′n) bằng υ. Tương tự như Định lý 2.14, định lý sau đây cho ta tính chất của số các lớp tương đương trên quan hệ ∼∗. Định lý 2.32. (1) Nếu p ≡ ±2 (mod 5) t