Mục lục
Lời cảm ơn ii
Mở đầu 1
Chương 1 . Dãy Fibonacci suy rộng 3
1.1 Phương trình sai phân tuyến tính cấp 2 . . . . . . . . . 3
1.2 Định nghĩa dãy Fibonacci suy rộng . . . . . . . . . . . 6
1.3 Một số tính chất của dãy Fibonacci suy rộng . . . . . . 7
Chương 2 . Tính chia hết của các số Fibonacci suy rộng 14
2.1 Kết quả của Hoggatt và Long . . . . . . . . . . . . . . 14
2.2 Kết quả của Aoki và Sakai . . . . . . . . . . . . . . . 18
2.3 So sánh với kết quả của Kôzaki và Nakahara . . . . . . 33
Kết luận 37
i
Tài liệu tham khảo 38
Lời cảm ơn
Luận văn được hoàn thành tại trường Đại học Khoa Học - Đại học
Thái Nguyên dưới sự hướng dẫn của TS. Ngô Văn Định, Trường Đại
học Khoa Học - Đại học Thái Nguyên.
Tôi xin bày tỏ lòng biết ơn sâu sắc nhất tới TS. Ngô Văn Định, người
đã định hướng chọn đề tài và tận tình hướng dẫn để tôi hoàn thành luận
văn này.
Tôi xin bày tỏ lòng biết ơn chân thành tới Phòng Đào tạo, các thầy
cô giáo dạy cao học chuyên ngành Phương pháp toán sơ cấp, trường
Đại học Khoa Học - Đại học Thái Nguyên đã giúp đỡ tôi trong suốt
quá trình học tập và hoàn thành luận văn tốt nghiệp.
Tôi xin được gửi lời cảm ơn chân thành tới gia đình, bạn bè, người
thân đã luôn động viên, cổ vũ, tạo mọi điều kiện thuận lợi cho tôi trong
quá trình học tập và hoàn thành luận văn.
Thái Nguyên, tháng 6 năm 2017
Tác giả
ii
Nguyễn Văn Quyên
Mở đầu
Dãy số Fibonacci {Fn} là dãy số được rất nhiều người biết đến,
quan tâm và nghiên cứu. Có rất nhiều tính chất thú vị của dãy số này
đã được tìm ra. Dãy số Fibonacci được định nghĩa bởi phương trình sai
phân tuyến tính cấp hai thuần nhất
Fn+2 = Fn+1 + Fn, n ≥ 0,
với điều kiện ban đầu F0 = F1 = 1. Khái niệm về dãy Fibonacci được
mở rộng theo nhiều cách khác nhau. Mục đích của luận văn này là trình
bày lại một số kết quả về một số dãy Fibonacci {xn} suy rộng xác định
bởi
xn+2 = pxn+1 + qxn, n ≥ 0,
với x0 = a, x1 = b, trong đó p, q, a, b là các số nguyên không âm.
Đầu tiên, Luận văn trình bày lại kết quả của Panwar, Singh và Gupta
[9] về một số tính chất thú vị của hai dãy Fibonacci suy rộng {Vn} và
{Un} được xác định bởi
Vn+2 = Vn+1 + 2Vn, n ≥ 0, với V0 = 2, V1 = 2,
và
1
Un+2 = Un+1 + 2Un, n ≥ 0, với U0 = 2, U1 = 0.
Tiếp theo, Luận văn trình bày một số kết quả của Hoggatt và Long [4]
về dãy Fibonacci suy rộng {un} được xác định bởi phương trình sai
phân
un+2 = pun+1 + qun, n ≥ 0, với u0 = 0, u1 = 1,
trong đó p, q là hai số nguyên dương. Cuối cùng, Luận văn trình bày lại
các kết quả của Aoki và Sakai [2, 3] về dãy Fibonacci suy rộng {Gn}
xác định bởi
Gn+2 = Gn+1 + Gn, n ≥ 1, với G1 = a, G2 = b,
trong đó a, b là hai số nguyên.
Cấu trúc của luận văn
Luận văn được trình bày thành 2 chương:
• Chương 1: Dãy Fibonacci suy rộng. Trong chương này, chúng tôi
trình bày sơ lược về lý thuyết về phương trình sai phân tuyến tính cấp
hai thuần nhất; khái niệm về dãy Fibonacci suy rộng và các kết quả
của Panwar, Singh và Gupta [9].
• Chương 2: Tính chia hết của các số Fibonacci suy rộng. Chương
này trình bày về một số kết quả của Hoggatt và Long [4]; các kết quả
2
của Aoki và Sakai [2, 3].
Chương 1
Dãy Fibonacci suy rộng
Trong chương mở đầu này, chúng tôi trình bày sơ lược về phương
trình sai phân tuyến tính cấp hai thuần nhất đặc biệt là về nghiệm của
phương trình trong trường hợp phương trình đặc trưng có hai nghiệm
phân biệt. Sau đó, chúng tôi trình bày khái niệm về dãy Fibonacci suy
rộng và các kết quả của Panwar, Singh và Gupta [9] về hai trường hợp
riêng của dãy Fibonacci suy rộng.
1.1 Phương trình sai phân tuyến tính cấp 2
Trong mục này, chúng tôi nhắc lại khái niệm về phương trình sai
phân tuyến tính cấp hai thuần nhất và đặc biệt chúng tôi trình bày về
công thức nghiệm của phương trình này trong trường hợp đa thức đặc
trưng có hai nghiệm phân biệt. Đây là những kiến thức cần thiết cho
các nội dung của các phần sau trong Luận văn. Nội dung về phương
trình sai phân chúng tôi tham khảo trong tài liệu [7].
Định nghĩa 1.1. Phương trình có dạng
3
(1.1) un+2 = Aun+1 + Bun, n = 1, 2, ...,
trong đó A, B là các hằng số, được gọi là phương trình sai phân tuyến
tính cấp hai thuần nhất.
Để tìm nghiệm của phương trình sai phân (1.1), chúng ta xét phương
trình bậc hai
α2 − Aα − B = 0. (1.2)
Phương trình bậc hai này được gọi là phương trình đặc trưng của
phương trình sai phân (1.1). Định lý sau đây cho chúng ta công thức
nghiệm của phương trình sai phân (1.1) trong trường hợp phương trình
đặc trưng (1.2) có hai nghiệm phân biệt. Ở đây, chúng tôi chỉ trình bày
nội dung của định lý để có thể sử dụng trong các phần sau mà không
trình bày chứng minh.
Định lý 1.2 ([7, Theorem 10.1]). Giả sử phương trình đặc trưng (1.2)
có hai nghiệm phân biệt α1 và α2. Khi đó phương trình sai phân (1.1)
có nghiệm là
1 + C2αn
2 , n = 1, 2, ...,
(1.3) un = C1αn
trong đó C1 và C2 là những số bất kì.
Chúng ta cũng cần chú ý rằng, nếu biết điều kiện ban đầu u0 và
u1 thì các hằng số C1 và C2 hoàn toàn được xác định. Khi đó, dãy số
n=1 được xác định bởi
{un}∞
2
1 − bαn−1 α1 − α2
aαn−1 , n ≥ 2, (1.4) un =
trong đó α1, α2 là hai nghiệm của phương trình đặc trưng (1.2) và
4
a = u2 − u1α2, b = u2 − u1α1. Công thức (1.4) được gọi là công thức
Binet của dãy {un}. Tên công thức này được đặt theo tên của nhà toán
học người Pháp Jacques Philippe Marie Binet do ông đã tìm ra công
thức Binet cho dãy Fibonacci vào thế kỷ 19.
Ví dụ 1.3. Ta sẽ xét ở đây một ví dụ rất quen thuộc về dãy số Fibonacci
{Fn} được xác định bởi phương trình sai phân
(1.5) Fn+2 = Fn+1 + Fn,
với điều kiện ban đầu F1 = 1, F2 = 1.
Phương trình đặc trưng của phương trình (1.5) là
λ2 − λ − 1 = 0.
Phương trình đặc trưng này có hai nghiệm phân biệt là √ √ 5 5 . và λ2 = λ1 = 1 + 2 1 − 2
√ Do đó, nghiệm tổng quát của phương trình (1.5) là √ (cid:33)n (cid:33)n (cid:32) (cid:32) 5 5 , n = 1, ... Fn = C1 + C2 1 + 2 1 − 2
√ √ (cid:32) Từ điều kiện ban đầu F1 = 1, F2 = 1 ta có hệ phương trình (cid:33) (cid:32) (cid:33) 5 5 = 1, C1 + C2 1 − 2
√ 1 + 2 √ (cid:33)2 (cid:33)2 (cid:32) (cid:32) 5 5 = 1. + C2 C1 1 + 2 1 − 2
. Từ đó suy ra số Giải hệ phương trình này ta được C1 = −C2 = 1 √ 5
5
√ √ hạng tổng quát của dãy số Fibonacci là (cid:34)(cid:32) (cid:33)n (cid:32) (cid:33)n(cid:35) 5 5 − , n = 1, 2, ... Fn = 1 + 2 1 − 2 1 √ 5
Ví dụ 1.4. Ta tiếp tục xét một ví dụ khác cũng là một dãy số quen
thuộc - dãy số Lucas {Ln}. Dãy Lucas cũng được xác định bởi phương
trình sai phân (1.5) nhưng với điều kiện ban đầu L0 = 2 và L1 = 1. Vì
vậy, số hạng tổng quát của dãy Lucas cũng có dạng:
2 , với n = 1, 2, ...,
1 + C2λn
Ln = C1λn
trong đó √ √ 5 5 . λ1 = và λ2 = 1 + 2
1 − 2 Với điều kiện ban đầu L0 = 2, L1 = 1, ta được: C1 + C2 = 2,
C1λ1 + C2λ2 = 1.
1 + λn
2 =
√ √ Giải hệ này ta được C1 = 1, C2 = 1. Vậy ta có (cid:32) (cid:33)n (cid:32) (cid:33)n 5 5 + . Ln = λn 1 + 2 1 − 2
1.2 Định nghĩa dãy Fibonacci suy rộng
Khái niệm của dãy Fibonacci được mở rộng dưới nhiều dạng khác
nhau. Chẳng hạn như, Kalman và Mena [6] đã nghiên cứu dãy số 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
6
Hn = Hn−1 + Hn−2, n ≥ 3, với H1 = p và H2 = p + q,
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
(1.6) Fk = pFk−1 + qFk−2, k ≥ 2,
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à:
7
Uk = Uk−1 + 2Uk−2, k ≥ 2, với U0 = 2, U1 = 0.
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
1 − Rk+1 2 R1 − R2
Rk+1 ; (i) Vk = 2
1 − Rk−1 2 R1 − R2
Rk−1 . (ii) Uk = 4
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à
1 − Rr+1 2 R1 − R2
8
Rr+1 , với mọi r thỏa mãn 0 ≤ r ≤ s. Vr = 2
Khi đó từ định nghĩa dãy Fibonacci suy rộng {Vn} ta có (lưu ý rằng R1
và R2 là hai nghiệm của phương trình x2 − x − 2 = 0)
1 − Rr+2 2 R1 − R2
Rr+2 . Vs+1 = Vs + 2Vs−1 = 2
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
n = (−1)n.
Fn−1Fn+1 − F 2
Sau đó, công thức này đã được nhà toán học người Bỉ Eugene Charles
n − Fn−rFn+r = (−1)n−rF 2 F 2 r .
Catalan tổng quát hóa thành
Đị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ó
n−1 = (−1)n−r+12n−rV 2
r−1;
(i) Vn−r−1Vn+r−1 − V 2
n+1 = (−1)n−r+12n−rU 2
r+1.
(ii) Un−r+1Un+r+1 − U 2
9
Chứng minh. Ta sẽ chứng minh đẳng thức (i), đẳng thức (ii) được
(cid:19)
(cid:19)2
(cid:19)
(cid:18)Rn
(cid:18)Rn+r
(cid:18)Rn−r
− 4
2
Vn−r−1Vn+r−1 − V 2
1 − Rn 2 R1 − R2 (cid:21)
=
+ 2(R1R2)n
−(R1R2)n
1 − Rn−r 2 R1 − R2 (cid:19)r (cid:18)R2 R1 (cid:19)r
1 − Rn+r 2 R1 − R2 (cid:19)r (cid:18)R1 R2 (cid:21)
=
− 2
n−1 = 2 (cid:20) 4 9 −4(−2)n 9
(cid:19)2
+ (cid:18)Rr
=
(cid:20)(cid:18)R2 R1 (−1)n+1−r2n+2 (−2)r
(cid:19)2
(cid:18)
.
2
= (−1)n+1−r2n−r
chứng minh tương tự. Sử dụng công thức Binet của dãy {Vn}, ta có
− (R1R2)n (cid:19)r (cid:18)R1 R2 1 − Rr 2 R1 − R2 1 − Rr Rr 2 R1 − R2 n−1 = (−1)n−r+12n−rV 2
r−1.
Vậy Vn−r−1Vn+r−1 − V 2
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ó
n−1 = (−1)n2n+1;
(i) Vn−2Vn − V 2
n+1 = (−1)n2n+3.
(ii) Un+2Un − U 2
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
1 + Rm
1 ), n chẵn, m lẻ,
bất kỳ, ta có
(i) Um+1Un − UmUn+1 =
1 + Rm
1 ), n lẻ, m chẵn;
10
(Rn 8 3 − (Rn 8 3
1 + Rm
1 ), n chẵn, m lẻ,
(Rn (ii) VmVn−1 − Vm−1Vn =
1 + Rm
1 ), n lẻ, m chẵn.
) − (Rm−1
)(Rn
Um+1Un − UmUn+1 =
2 )(cid:3)
1 − Rn
1 − Rm
2
=
2 )(Rn−1 1 Rn−1
1 − Rm
1 − Rm−1 2 (cid:3) 2 Rn−1 1
2 Rn
2 − Rm (cid:17)
=
(Rm
1 Rm 2 )
1 − Rn−1 2 + Rm−1 2 − Rn
1 Rn
=
2 ).
1 Rm
1 Rn − 1 R2 2 − Rn
4 3 (Rn − 4 3
Từ đây suy ra
1 + Rm
1 ), n chẵn, m lẻ,
Um+1Un − UmUn+1 =
(Rn
8 3 −
1 + Rm
1 ), n lẻ, m chẵn.
(Rn 8 3
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ó 16 (cid:2)(Rm 9 16 (cid:2)Rm−1 9 (cid:16) 1 16 R1 9 8 1 Rn (Rm 3
Đị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ó
(cid:17) 1. = R1; lim k→∞
(cid:17) 2. = R1. (cid:16) Vk−1 Vk−2 (cid:16) Uk+1 Uk lim k→∞
Chứng minh. 1. Sử dụng công thức Binet ta có
(cid:17)k 1 − (cid:19)
1 − Rk Rk 2 1 − Rk−1 Rk−1
2
1 R1
1 R2
11
(cid:17)k lim k→∞ = lim k→∞ = lim k→∞ (cid:18)Vk−1 Vk−2 − (cid:16) R2 R1 (cid:16) R2 R1
(cid:17)k = 0 vì |R2| < R1. Từ đó, ta thu được điều phải (cid:16) R2 R1 Ta có lim k→∞
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ó
2k + V 2
2k+2 = 8 9
(cid:104) (cid:105) 34(16)k + 10(4)k + 1 1. V 2
2k − V 2
2k+2 = −16 9
(cid:104) 12(16)k + (4)k(cid:105) 2. V 2
(cid:104)
− 2(R1R2)2k+1 + R4k+6
2k+V 2 V 2
R4k+2 1
+ R4k+2 2
1
=
(cid:0)1 + R4k
(cid:1) + R4k+2
+ R4k+6 2 (cid:1) − 2(R1R2)2k+1 (cid:110)
− 2(R1R2)2k+3(cid:105) 1 + (R1R2)2(cid:111)(cid:105)
1
2
4 9 R4k+2 1
2
(cid:104)
=
(cid:0)1 + R4k − 10(R1R2)2k+1(cid:105)
17R4k+2 1
+ 2R4k+2 2
(cid:104)
=
2 + 20(R1R2)2k(cid:105)
1 + 2R4k
(cid:104)
=
(cid:104)
=
68R4k 68(16)k + 2 + 20(4)k(cid:105) 34(16)k + 1 + 10(4)k(cid:105)
.
2k+2 = (cid:104) 4 9 4 9 4 9 4 9 8 9
Chứng minh. 1. Sử dụng công thức Binet, ta có
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
12
suy rộng {Un}.
Định lý 1.12. Với dãy {Uk}k≥0 ta có
2k + U 2
2k+2 = 16 9
4 (16)k + 5(4)k(cid:105) (cid:104) 17 5(4)2k−1 + (4)k(cid:105) (cid:104)
; 1. U 2
2k − U 2
2k+2 = −48 9
13
2. U 2 .
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
14
. α = và β = p + (cid:112)p2 + 4q 2 p − (cid:112)p2 + 4q 2
Do đó, công thức Binet cho dãy {un} là
, n ≥ 0. un = αn − βn α − β
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ới m ≥ 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 đó
15
uk+1 = puk + quk−1.
Đ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ó
[(n−1)/2] (cid:88)
(cid:19)
i=0
pn−2i−1qi. un = (cid:18)n − i − 1 i
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
p0q0 = 1 = u1. 0
Giả sử đẳng thức đúng với n = k −1 và n = k, với k cố định và k ≥ 1.
Khi đó
[(k−2)/2] (cid:80) i=0
k − i − 2 = pk−2iqi + pk−2i−2qi+1 uk+1 = puk + quk−1 k − i − 1 [(k−1)/2] (cid:80) i=0 i i
[(k−1)/2] (cid:80) i=0
[k/2] (cid:80) i=0
k − i − 1 k − i − 2 = pk−2iqi + pk−2iqi i − 1
[k/2] (cid:80) i=0
k − i = i pk−2iqi. i
Do đó kết quả đúng với n = k + 1, và do đó cũng đúng với mọi
16
n ≥ 0. Điều phải chứng minh.
Định lý 2.5. Với n ≥ m ≥ 2, ta có um | un khi và chỉ khi m | 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ếu m|n. Giả sử rằng m ≥ 2 và um|un. Nếu m (cid:45) 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ới m ≥ 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
17
urm = u(m,n)+(−s)n
= 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
(2.1) G1, G2 ∈ Z và Gn+2 = Gn+1 + Gn với mọi n ≥ 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;
18
(2) nếu p ≡ ±2( mod 5) thì Fp+1 ≡ 0 mod p.
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
n} là hai dãy Fibonacci suy rộng thỏa
ngôi sau đây:
2. Nếu
1, G(cid:48)
−1
−1 ≡ G(cid:48)
Định nghĩa 2.8. Cho {Gn}và {G(cid:48) mãn p không là ước của G1, G2 và p không là ước của G(cid:48)
n}.
2G(cid:48)
1
G2G1 mod p thì ta viết {Gn} ∼ {G(cid:48)
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 (cid:45) G1, G2}/ ∼ .
Theo định nghĩa của quan hệ ∼, mỗi lớp {Gn} ∈ Xp chứa vô
p | = p − 1.
hạn các dãy Fibonacci suy rộng. Số lớp tương đương {Gn} của Xp là |Xp| = |F×
Kí hiệu Yp là tập con của Xp xác định bởi (cid:110) (cid:111) . Yp = {Gn} ∈ Xp|p (cid:45) Gn, ∀n ∈ N
Bổ đề sau đây cho ta thấy điều kiện "p không là ước của Gn 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.
n}. Khi đó chúng ta có p không là ước của Gn
2 và {Gn} ∼ {G(cid:48)
1, G(cid:48)
Bổ đề 2.9. Giả sử p không là ước của G1, G2, p không là ước của G(cid:48)
n với mọi n ∈ N.
19
khi và chỉ khi p không là ước của G(cid:48)
−1
1
2G(cid:48)
1 ≡ G(cid:48)
Chứng minh. Cho a là số nguyên tố thỏa mãn a ≡ G2G−1
n ≡ AnG(cid:48) cho G1 và G(cid:48)
(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(cid:48) 1 (mod p) với mọi n ∈ N. Ngược lại nếu p không chia hết 1 chúng ta có p|Gn khi và chỉ khi p|G(cid:48) n.
Với mọi i nguyên dương thỏa mãn i (cid:54)≡ 0 mod d(p), gọi gi(0 ≤
i mod p.
gi ≤ p − 1) là số nguyên thỏa mãn gi ≡ Fi+1F −1
Bổ đề 2.10. Cho i và j là các số nguyên dương thỏa mãn i, j (cid:54)≡ 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, ...,
20
Fj, Fj+1 ≡ J2Fj, Fj+2 ≡ J3Fj, Fj+3 ≡ J4Fj, ...
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 (cid:54)≡ 0 (mod d(p)) bởi i, j (cid:54)≡
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.
2
p+1 2
+ (cid:1), chúng ta nhận được F 2 Chứng minh. Áp dụng tính chất Fn+m = FmFn+1+Fm−1Fn với (n, m) = (cid:0) p−1 2 , p+3
2 , p+1 2 = Fp và F 2
p+3 2
p+1 2
p−1 2
(cid:1) và (n, m) = (cid:0) p+1 + F 2 F 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ừ
2
2
p+1 2
p+3 2
p+1 2
21
(cid:16) (cid:17)2 + F 2 mod p = F p+1 + F p−1 + F 2 −1 ≡ F 2
p+1 2
− 1 + F 2 mod p, ≡ 2F p+1 2 F p−1 2
2
2
(cid:16) (cid:17) mod p ≡ 0 mod p do đó F p+1 suy ra F p+1 2F p−1 2 − F p+1 2 ≡ −2F p−1 2
p−1 2
p+1 2
p−1 2
+ F 2 ≡ 5F 2 vì d(p) = p + 1. Chúng ta nhận được −1 ≡ F 2
p−1 2
(cid:33) (cid:32)5F 2 (cid:19) (cid:19) (cid:19) (cid:17) = = = = 1. = −1 và mod p. Nếu chúng ta giả sử p ≡ 1 mod 4 thì chúng ta có (cid:18)−1 p (cid:18)±2 5 (cid:18)5 p (cid:16)p 5 p
p−1 2
≡ −1 (mod p). Do đó ta có được p ≡ 3 Điều này mâu thuẫn với 5F 2
(mod 4).
2 ≡ gn−2
Mệnh đề 2.12. Giả sử p (cid:45) G1, G2. Với mọi số nguyên dương n thỏa mãn n (cid:54)≡ 2 mod d(p). Chúng ta có p|Gn khi và chỉ khi −G1G−1
(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.
2 ≡ gi (mod p) với 1 ≤ i ≤ d(p) − 2.
Mệnh đề 2.13. Giả sử p (cid:45) G1, G2. Chúng ta có p|Gn với n ∈ N khi và chỉ khi −G1G−1
Chứng minh. Nếu n ≡ 2 (mod d(p)), khi đó ta có Gn = Fn−2G1 +
Fn−1G2 ≡ Fn−1G2 (cid:54)≡ 0 (mod p). Hơn thế nữa nếu i = d(p) − 1 thì (cid:54)≡ gi(mod p) do chúng ta đã giả thiết p (cid:45) G1 và gd(p)−1 ≡
d(p)−1 ≡ 0 (mod p). Vì vậy ta chỉ cần chứng minh rằng p|Gn với 2 ≡ gi(mod
−G1G−1 2 Fd(p)F −1 n ∈ N thỏa mãn n (cid:54)≡ 2(mod d(p)) khi và chỉ khi −G1G−1
p) với i thỏa mãn 1 ≤ i ≤ d(p) − 1. Điều này được suy ra từ Mệnh đề
22
2.12 và Bổ đề 2.10.
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} =
(cid:111) (cid:110) {G(1, k)}|1 ≤ k ≤ p − 1 . {G(1, 3)}. Chúng ta có thể viết Xp =
Định lý 2.14. Với các kí hiệu như trên, ta có
(cid:110) (cid:111) ; (1) Yp = Xp − {G(1, gi)}|1 ≤ i ≤ d(p) − 2
d(p)−i−1 (mod
(2) |Yp| = p + 1 − d(p).
(cid:111)
(cid:110)
{Gn} ∈ Xp|p|Gn, n ∈ N
Yp = Xp −
(cid:111)
(cid:110)
{G (1, k)}|1 ≤ k ≤ p − 1, −k−1 ≡ gi(modp); 1 ≤ i ≤ d(p) − 2
= Xp −
(cid:111)
(cid:110)
= Xp −
{G (1, k)}|1 ≤ k ≤ p − 1, −k−1 ≡ gd(p)−i−1(modp); 1 ≤ i ≤ d(p) − 2 (cid:111)
(cid:110)
{G (1, k)}|1 ≤ k ≤ p − 1, k ≡ −g−1
= Xp −
d(p)−i−1(modp); 1 ≤ i ≤ d(p) − 2
(cid:111)
(cid:110)
.
= Xp −
{G (1, gi)}|1 ≤ i ≤ d(p) − 2
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−1 p). Theo Bổ đề 2.10 và Mệnh đề 2.13, chúng ta có
(2) Theo Bổ đề 2.10, ta có gi (cid:54)= gj nếu 1 ≤ i, j ≤ d(p) − 2 và i (cid:54)= 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.
(1) |Y5| = 1. Hệ quả 2.15.
(2) Nếu p ≡ ±1 mod 5 thì chúng ta có vô hạn dãy Fibonacci suy
23
rộng {Gn} thỏa mãn p (cid:45) Gn với mọi n ∈ N.
(3) Nếu p ≡ ±2 mod 5 và d(p) = p + 1, thì với mọi dãy Fibonacci
n) là hai dãy Fibonacci suy rộng xác
n) nếu có hai số nguyên m
suy rộng {Gn}, ta có p|Gn với mọi n ∈ N.
n ≡ G(cid:48)
n+1Gm (mod p).
Định nghĩa 2.16. Cho (Gn) và (G(cid:48) định bởi (2.1). Chúng ta viết (Gn) ∼∗ (G(cid:48) và n thỏa mãn Gm+1G(cid:48)
Từ định nghĩa của hai quan hệ ∼ và ∼∗, ta suy ra:
n) thì ta có (Gn) ∼∗ (G(cid:48)
n).
Bổ đề 2.17. Nếu (Gn) ∼ (G(cid:48)
Chú ý rằng nếu dãy (Gn) thỏa mãn p | G1 và p | G2 thì chúng ta
n) và (Gn) ∼∗ (G(cid:48)
n) với mọi dãy Fibonacci suy rộng
có (Gn) ∼ (G(cid:48)
n) xác định bởi (2.1). Ở trên ta thấy ∼ là một quan hệ tương đương
(G(cid:48)
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 (cid:45) G1 hoặc p (cid:45) 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:
n ≡ G(cid:48)
n+1 ≡
n) là hai dãy Fibonacci suy rộng xác n+1Gm( mod p) thì Gm+2G(cid:48)
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 (cid:45) G1 hoặc p (cid:45) G2. Nếu p|Gn thì p (cid:45) Gn−1 và p (cid:45) Gn+1.
n+2Gm+1( mod p).
24
Bổ đề 2.19. Cho (Gn) và (G(cid:48) định bởi (2.1). Nếu Gm+1G(cid:48) G(cid:48)
(cid:48)
Chứng minh.
n+1 = (Gm+1 + Gm)G
(cid:48) n+1
(cid:48)
Gm+2G
(cid:48) n+1
n+1 + GmG
(cid:48)
= Gm+1G
(cid:48) n+1 + Gm+1G n
(cid:48)
(cid:48)
≡ Gm+1G
n+1 + G
n)
(cid:48)
= Gm+1(G
n+2.
= Gm+1G
n) và
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 (cid:45) G1 hoặc p (cid:45) G2.
n). Theo giả thiết tồn tại các số nguyên
n) thì (Gn) ∼∗ (G(cid:48)(cid:48)
n) ∼∗ (G(cid:48)(cid:48)
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(cid:48) (G(cid:48)
(cid:48)
(cid:48)(cid:48)
(cid:48)(cid:48)
(cid:48)
(cid:48)
(cid:48)
m, n, k, l thỏa mãn
n ≡ G
n+1Gm mod p và G
k+1G
l ≡ G
l+1G
k mod p.
Gm+1G
Đặt t = max(n, k). Theo Bổ đề 2.19, ta suy ra các số nguyên m và l
(cid:48)
(cid:48)(cid:48)
(cid:48)(cid:48)
(cid:48)
(cid:48)
(cid:48)
thỏa mãn
t ≡ G
t+1Gm mod p và G
t+1G
l ≡ G
l+1G
t mod p.
(2.2) Gm+1G
t thì ta có p (cid:45) G(cid:48)
t+1 theo Bổ đề 2.18. Từ (2.2) ta có
Giả sử nếu p|G(cid:48)
n)vì Gm+1G(cid:48)(cid:48)
l . Vì vậy chúng ta có (Gn) ∼∗ (G(cid:48)(cid:48)
l ≡ 0 ≡
25
p|Gm và p|G(cid:48)(cid:48)
t+1 thì bằng cách lập luận tương
l+1Gm mod p. Nếu ta giả thiết p|G(cid:48)
n). Tiếp theo chúng ta giả sử p (cid:45) G(cid:48)
t và p (cid:45) G(cid:48)
t+1.
G(cid:48)(cid:48)
l từ (2.2). Do đó chúng ta
tự ta có (Gn) ∼∗ (G(cid:48)(cid:48) Khi đó chúng ta có được p (cid:45) Gm và p (cid:45) G(cid:48)(cid:48)
m ≡ G(cid:48)
t+1G
l ≡
l+1Gn−1 l
mod p và do đó Gm+1G(cid:48)(cid:48)
n).
(cid:48)−1 t ≡ G(cid:48)(cid:48) l+1Gm mod p. Đồng dư này có nghĩa (Gn) ∼∗ (G(cid:48)(cid:48)
n) là hai dãy Fibonacci suy rộng xác định n) và p (cid:45) Gn
có Gm+1G−1 G(cid:48)(cid:48)
n với mọi n ∈ Z.
Bổ đề 2.21. Giả sử (Gn), (G(cid:48) bởi (2.1) thỏa mãn p (cid:45) G1 hoặc p (cid:45) G2. Nếu (Gn) ∼∗ (G(cid:48) với mọi n ∈ Z thì chúng ta có p (cid:45) G(cid:48)
l. Do
n mod p), chúng ta có thể giả sử l ≥ n. Sử dụng
l+1Gk
l ≡ G(cid:48)
Chứng minh. Giả sử rằng tồn tại hai số nguyên m, n thỏa mãn Gm+1G(cid:48) n ≡ G(cid:48) n+1Gm (mod p). Giả sử rằng tồn tai số nguyên l sao cho p|G(cid:48)
l+1 nên suy ra p|Gk. Mẫu
l và không chia hết G(cid:48)
tính tuần hoàn của (G(cid:48) Bổ đề 2.19, ta suy ra tồn tại số nguyên k sao cho Gk+1G(cid:48) (mod p).Vì p chia hết G(cid:48)
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ố
26
nguyên m và n thỏa mãn Gm+1Fn ≡ Fn+1Gm (mod p). Mặt khác, vì
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 (cid:45) 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 ∼∗:
p = {(Gn) | p (cid:45) G1 hoặc p (cid:45) G2}/ ∼∗ .
X ∗
p = {(Gn) ∈ X ∗ Y ∗
p | p (cid:45) Gn với mọi n ∈ Z}.
Đặt
p = Y ∗
p ∪ {(Fn)}.
p , ta có thể chọn phần tự đại
(1) X ∗ Bổ đề 2.23.
(2) Với mọi lớp tương đương (Gn) của X ∗ diện (Gn) thỏa mãn p (cid:45) G1, G2.
p . Với mọi dãy (G(cid:48)
n) ∈
(3) Cho (Gn) là một lớp tương đương của Y ∗
1, G(cid:48) 2.
(Gn), ta có p (cid:45) G(cid:48)
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((cid:54)= 2, 5) là một số nguyên tố.
(1) Nếu p ≡ ±1( mod 5), khi đó X 2 − X − 1 = 0 có hai nghiệm
27
phân biệt trong Fp.
(2) Nếu p ≡ ±2( mod 5), khi đó X 2 − X − 1 = 0 vô nghiệm trong
Fp.
√ Chứng minh. Nghiệm của X 2 − X − 1 = 0 trong Fp (bao đóng đại số của Fp) là X = 2−1(1 ±
√ √ khác nhau. Chúng ta có 2−1(1±
5
(cid:17) = (cid:0) p thế nữa điều này tương đương với 5). Do giả thiết p (cid:54)= 2, 5 nên các nghiệm này 5 ∈ Fp. Hơn (cid:1) = 1, tức là p ≡ ±1(mod 5) ∈ Fp khi và chỉ khi (cid:16) 5 p
5).
(1) Với bất kì số nguyên n thỏa mãn n (cid:54)≡ 0 mod d(p), Định nghĩa 2.25.
chúng ta định nghĩa số nguyên fn(0 ≤ fn ≤ p − 1) thỏa mãn
n mod p.
fn ≡ Fn+1F −1
(2) Cho (Gn) là dãy Fibonacci suy rộng xác định bởi (2.1) thỏa mãn p (cid:45) Gn với mọi n ∈ Z. Chúng ta có thể định nghĩa số nguyên
n mod p.
gn(1 ≤ gn ≤ p − 1) sao cho gn ≡ Gn+1G−1
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ó
n+1 − GnGn+1 − G2
n = −(G2
n − Gn−1Gn − G2
n−1).
G2
28
Để đơn giản, chúng ta đưa ra một kí hiệu mới. Nếu (Gn) là một dãy
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 (cid:45) Gn với mọi n ∈ Z. Giả sử thêm rằng a và b thỏa mãn b2 − ab − a2 (cid:54)≡ 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
n−m ≡ 0 (mod p).
mF 2
m+1Fn−m − GmGm+1(Fn−m+1 − Fn−m−1) − G2
G2
(2.3)
Theo Bổ đề 2.27,với vế trái của (2.3), chúng ta có
mFn−m
m+1Fn−m − GmGm+1(Fn−m+1 − Fn−m−1) − G2
G2
m+1Fn−m − GmGm+1Fn−m − G2
mFn−m
≡ G2
m+1 − GmGm+1 − G2
m)Fn−m
≡ (G2
2 − G1G2 − G2
1)Fn−m
≡ (−1)m−1(G2
≡ (−1)m−1(b2 − ab − a2)Fn−m mod p.
Theo giả thiết b2 − ab − a2 (cid:54)≡ 0 mod p, ta suy ra gn = gm khi và chỉ
29
khi n ≡ m mod d(p).
Định nghĩa 2.29. Giả sử (Gn = (G(a, b))) thỏa mãn p (cid:45) 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 (cid:45) 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 (cid:54)≡ 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−1 n+1
≡ (Gn+1 + Gn)(Gn + Gn−1)−1
n + 1)(1 + Gn−1G−1
n )−1
≡ (Gn+1G−1
n−1)−1
≡ (gn + 1)(1 + g−1
30
≡ (ba−1 + 1)(1 + b−1a)−1 ≡ (ba−1 + 1) × (cid:8)b−1a(ba−1 + 1)(cid:9)−1
≡ ba−1 ≡ g1 mod p.
Mặt khác 1 ≤ g1, gn+1 ≤ p − 1, chúng ta có gn+1 = g1.
n) thỏa mãn p (cid:45) Gn, G(cid:48) n với mọi n. Khi đó ta có (Gn) ∼∗ (G(cid:48) n)
Bổ đề 2.31. Giả sử rằng (Gn) và (G(cid:48) n ∈ Z. Cho υ là chu kì thứ hai của G(cid:48)
n = g1(≡
khi và chỉ khi tồn tại số nguyên n với (1 ≤ n ≤ υ) sao cho g(cid:48)
1 mod p).
−1
n
n = g1 với một số nguyên n−1G(cid:48) ≡ G2G−1
1 mod p
G2G−1
n). Khi đó phải tồn tại hai
n). Tiếp theo, chúng ta giả sử (Gn) ∼∗ (G(cid:48) n ≡ G(cid:48)
n+1Gm mod p. Theo Bổ
n ≡ G(cid:48)
n+1G1 mod p.
Chứng minh. Đầu tiên, chúng ta giả sử g(cid:48) n(1 ≤ n ≤ υ). Khi đó chúng ta có được G(cid:48) và do đó (Gn) ∼∗ (G(cid:48)
n do
n ≡ g1 mod p. Chúng ta có g1 = g(cid:48)
số nguyên m và n sao cho Gm+1G(cid:48) đề 2.19, tồn tại một số nguyên n sao cho G2G(cid:48) Vì thế chúng ta có được g(cid:48)
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(cid:48) 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ệ ∼∗.
(1) Nếu p ≡ ±2 (mod 5) thì ta có Định lý 2.32.
p | =
31
= − 1. |Y ∗ |Yp| d(p) p + 1 d(p)
(2) Nếu p ≡ ±1 (mod 5) thì ta có
p | = 2 +
|Y ∗ = + 1. |Yp| − 2 d(p) p − 1 d(p)
p | = |Yp| = 1.
(3) Nếu p = 5 thì ta có |Y ∗
Chứng minh. Khẳng định (3) được suy ra trực tiếp từ Hệ quả 2.15.
(cid:48)
Chúng ta sẽ chứng minh (1) và (2). Theo Định lý 2.14 ta có
p −
(cid:48)
(cid:111) (cid:110) , G(1, fi)|1 ≤ i ≤ d(p) − 2 Yp = X
X
p = {(Gn)|p (cid:45) G1; p (cid:45) G2} / ∼ (cid:111)
(cid:110) = (G(1, b))|1 ≤ b ≤ p − 1 .
• Chứng minh (1): Chúng ta xét lớp tương đương (Gn)((Gn) =
(G(1, b))) của Yp. Vì p ≡ ±2 mod (5), ta có b2 − b − 1 (cid:54)≡ 0 mod p bởi vì X 2 − X − 1 = 0 không có nghiệm trong Fp theo Bổ đề
2.24. Do đó chúng ta có chu kỳ thứ hai của (Gn) là d(p) theo Hệ quả
2.30 và g1, g2, ..., gd(p) là các giá trị khác nhau theo Định lý 2.28, trong
(mod p) và 1 ≤ gn ≤ đó gn là số nguyên sao cho gn = Gn+1G−1 n
p − 1. Từ định nghĩa về quan hệ ∼∗, chúng ta có (Gn) = (G(1, b)) ∼∗
n = (G(1, b(cid:48)))) của Yp thỏa mãn b(cid:48) (cid:54)≡ g1, ..., gd(p) (mod
n)((G(cid:48) đương (G(cid:48) p), chúng ta có (Gn) (cid:54)∼∗ (G(cid:48)
n) theo Bổ đề 2.31. Như vậy với bất kì lớp
(G(1, gi)) với mọi i (1 ≤ i ≤ d(p)). Mặt khác với bất kì lớp tương
p đều sinh ra d(p) lớp (G(1, gi))(1 ≤ i ≤ d(p)) dưới
(G(1, b)) trong Y ∗
p | = |Yp|
d(p). Khẳng
quan hệ tương đương ∼ . Do đó chúng ta có được |Y ∗
|Yp| d(p) = p+1
d(p) − 1 được suy ra từ Định lý 2.14.
32
định
• Chứng minh (2): Nếu p ≡ ±1(mod 5) thì X 2 − X − 1 = 0 có hai nghiệm phân biệt α và β trong Fp theo Bổ đề 2.24. Chúng ta xét dãy Fibonacci suy rộng (G(1, α)) = (Gn). Ta có p (cid:45) Gn với mọi n ∈ Z vì
α2 − α − 1 ≡ 0 (mod p). Vì vậy theo Bổ đề 2.18 và Hệ quả 2.30 Chúng
ta có (G(1, α)) ∈ Yp. Tương tự như vậy, chúng ta có (G(1, β)) ∈ Yp.
Cho b là số nguyên thỏa mãn 1 ≤ b ≤ p − 1. Khi đó chu kỳ thứ hai
của (G(1, α)) và (G(1, β)) bằng 1 theo Hệ quả 2.30. Do đó chúng ta
có (G(1, b)) ∼∗ (G(1, α)) khi và chỉ khi b = α theo Bổ đề 2.31. Bằng
những lập luận này, chúng ta có kết quả tương tự với (G(1, β)). Mặt
khác, d(p)lớp (G(1, b)) của Yp thỏa mãn b (cid:54)= α, β cũng là lớp của Y ∗ p .
p | = 2 + |Yp|−2
d(p) và đẳng thức sau được suy ra từ
Như vậy chúng ta có |Y ∗
Định lý 2.14.
2.3 So sánh với kết quả của Kôzaki và Nakahara
Định nghĩa 2.33. Một số nguyên m được gọi là kiểu không ước (the
type of a non-divisor) nếu tồn tại dãy Fibonacci suy rộng (Gn) xác định bởi (2.1) sao cho m (cid:45) Gn với mọi n ∈ Z.
Với một số nguyên tố p, kí hiệu k(p) là chu kỳ của (Fn mod p).
Năm 1999, Kôzaki và Nakahara [8] đã chứng minh được kết quả sau:
Định lý 2.34 (Định lý Kôzaki và Nakahara). Một số nguyên tố p là
kiểu không ước khi và chỉ khi một trong những điều kiện sau đây thỏa
mãn.
33
(1) p = 5.
(2) p ≡ 1, 9, 11, 13, 17, 19 (mod 20).
(3) p ≡ 3, 7(mod 20) và k(p) < 2(p + 1).
Ta sẽ chỉ ra rằng kết quả này của Kôzaki và Nakahara có thể được
suy ra từ kết quả của Aoki và Sakai. Thật vậy, từ Định lý 2.14 và Hệ
quả 2.15 ta suy ra hệ quả sau đây:
Hệ quả 2.35. Một số nguyên tố p là kiểu không ước khi và chỉ khi một
trong những khẳng định sau đây thỏa mãn.
(1) p = 5.
(2) p ≡ ±1 (mod 5).
(3) p ≡ ±2 (mod 5) và d(p) < p + 1.
Chúng ta sẽ chứng minh Định lý 2.34 tương đương với Hệ quả 2.35.
Cụ thể hơn, chúng ta sẽ chứng minh một trong ba điều kiện trong Định
lý 2.34 được thỏa mãn nếu và chỉ nếu một trong ba điều kiện trong Hệ
quả 2.35 được thỏa mãn.
Đầu tiên, Chúng ta chứng minh rằng nếu (1) hoặc (2) hoặc (3) của
Định lý 2.34 được thỏa mãn thì (1) hoặc (2) hoặc (3) của Hệ quả 2.35
được thỏa mãn. Điều này hiển nhiên đúng nếu điều kiện (1) của Định
lý 2.34 được thỏa mãn.
Giả sử rằng điều kiện (2) của Định lý 2.34 được thỏa mãn. Nếu p ≡
34
1, 9, 11, 19 (mod 20) thì chúng ta có p ≡ ±1 (mod 5). Nếu p ≡ 13, 17
(mod 20) thì chúng ta có p ≡ ±2 (mod 5) và p ≡ 1(mod 4). Theo Bổ
đề 2.7 và Bổ đề 2.11 ta có d(p) < p + 1.
Chúng ta giả sử điều kiện (3) của Định lý 2.34 được thỏa mãn.
Trong trường hợp này ta có p ≡ 3 (mod 4) và p ≡ ±2 (mod 5). Bởi
vì p ≡ ±2 (mod 5), chúng ta có Fp ≡ −1 (mod p) và Fp+1 ≡ 0
(mod p), do đó chúng ta có được k(p) (cid:54)= p + 1. Nếu d(p) = p + 1
thì ta có p + 1|k(p) do d(p)|k(p). Tuy nhiên điều này mẫu thuẫn vì
k(p) (cid:54)= p + 1, k(p) < 2(p + 1) và k(p)|2(p + 1) được thỏa mãn. Do đó
d(p) < p + 1.
Tiếp theo, chúng ta chứng minh rằng nếu (1) hoặc (2) hoặc (3) của
Hệ quả 2.35 được thỏa mãn thì một trong ba điều kiện (1), (2) hoặc
(3) của Định lý 2.34 được thỏa mãn. Hiển nhiên điều này đúng khi (1)
của Hệ quả 2.35 được thỏa mãn. Chúng ta giả sử rằng điều kiện (2)
của Hệ quả 2.35 được thỏa mãn. Nếu p ≡ 1 (mod 5) thì chúng ta có
p ≡ 1, 11(mod 20). Nếu p ≡ −1 (mod 5) thì chúng ta có p ≡ 9, 19
(mod 20).
Cuối cùng chúng ta giả sử rằng (3) của Hệ quả 2.35 được thỏa mãn.
Khi p ≡ −2(mod 5) thì p ≡ 7, 17 (mod 20). Khi p ≡ −2(mod 5)
chúng ta có p ≡ 3, 13(mod 20). Nếu p ≡ 13, 17(mod 20) thì điều
kiện (2) của Định lý 2.34 được thỏa mãn. Chúng ta xét trường hợp
p ≡ 3, 7(mod 20). Trong trường hợp này chúng ta có p ≡ 3(mod 4) và
p ≡ ±2(mod 5), và do đó k(p)|2(p+1). Từ công thức Fn−1Fn+1−F 2
n = d(p) ≡ (−1)d(p) (mod p).
35
(−1)n, chúng ta có được Fd(p)−1Fd(p)+1 − F 2
Do đó chúng ta có được F 2
d(p)−1 ≡ (−1)d(p)(mod p) vì Fd(p) ≡ 0 (mod d(p)−1 ≡ −1(mod p) thì mâu
p) và Fd(p)−1 ≡ Fd(p)+1(mod p). Nếu F 2
d(p)−1 ≡ 1(mod p)
(cid:17) thuẫn với = −1 do p ≡ 3(mod 4). Nếu F 2 (cid:16) −1 p
thì Fd(p)−1 ≡ ±1(mod p) được thỏa mãn. Trong trường hợp Fd(p)−1 ≡
1(mod p), chúng ta có k(p) = d(p), và do đó k(p) < p + 1. Trong
trường hợp Fd(p)−1 ≡ −1(mod p), chúng ta có k(p) ≤ 2d(p) < 2(p+1)
36
vì F2d(p)−1 ≡ 1(mod p).
Kết luận
Luận văn đã trình bày được một số vấn đề sau:
1. Khái niệm về dãy Fibonacci suy rộng; Một số tính chất thú vị của
hai dãy Fibonacci suy rộng {Vn} và {Un} được xác định bởi
Vn+2 = Vn+1 + 2Vn, n ≥ 0, với V0 = 2, V1 = 2,
và
Un+2 = Un+1 + 2Un, n ≥ 0, với U0 = 2, U1 = 0;
2. Một số kết quả của Hoggatt và Long [4] về dãy Fibonacci suy
rộng {un} được xác định bởi phương trình sai phân
un+2 = pun+1 + qun, n ≥ 0, với u0 = 0, u1 = 1,
trong đó p, q là hai số nguyên dương;
3. Các kết quả của Aoki và Sakai [2, 3] về dãy Fibonacci suy rộng
{Gn} xác định bởi
Gn+2 = Gn+1 + Gn, n ≥ 1, với G1 = a, G2 = b,
37
trong đó a, b là hai số nguyên.
Tài liệu tham khảo
Tiếng Việt
[1] Hà Huy Khoái, Phạm Huy Điển (2003), Số học thuật toán, NXB
Đại học Quốc gia Hà Nội.
Tiếng Anh
[2] Aoki M. and Sakai Y. (2015), "On divisibility of genneralized
Fibonacci numbers", Integers 15, Paper No. A31.
[3] Aoki M and Sakai Y. (2016), "On equivalence class of genner-
alized fibonacci sequences", Journal of Integer Sequences, Vol.
19, Article 16.2.6.
[4] Hoggatt E. V. and Long C. T. (1974), "Divisibility properties of
genneralized Fibonacci polynomial", April ,113–120.
[5] Horadam A. F. (1961), “The Generalized Fibonacci Sequences",
The American Math. Monthly, 68, No. 5, 455–459.
[6] Kalman D. and Mena R. (2002), “The Fibonacci Numbers – Ex-
38
posed", The Mathematical Magazine, 2.
[7] Koshy T. (2001), Fibonacci and Lucas numbers with Applica-
tions, John Wiley & Sons, Inc., Toronto.
[8] Kôzaki M. and Nakahara T. (1999), “On arithmetic properties
of generalized Fibonacci sequences", Reports of the Faculty of
Science and Engineering, Saga University, Mathematics 28, 1—
18.
[9] Panwar K. Y., Singh B and Gupta K V. (2014), "Generalized Fi-
bonacci sequences and its properties", Palestine Journal of Math-
39
ematics, 3(1), 144–147.
