ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC --------------------------- PHẠM THỊ HỒNG
DÃY FIBONACCI MODULO m
LUẬN VĂN THẠC SĨ TOÁN HỌC
THÁI NGUYÊN - 2019
ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC ---------------------------
PHẠM THỊ HỒNG
DÃY FIBONACCI MODULO m
Chuyên ngành: Phương pháp Toán sơ cấp
Mã số: 8 46 01 13
LUẬN VĂN THẠC SĨ TOÁN HỌC
NGƯỜI HƯỚNG DẪN KHOA HỌC
TS. NGUYỄN DUY TÂN
THÁI NGUYÊN - 2019
iii
Mục lục
Mở đầu 1
.
1 Một số kiến thức chuẩn bị . . . . . . . .
. . 1.1. Dãy Fibonacci 1.2. Công thức Binet . . 1.3. Luật thuận nghịch bậc hai . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 3 7 8
2 Dãy Fibonacci mod m
. . . . . . .
2.1. Một số tính chất cơ bản . . 2.2. Chu kỳ của dãy Fibonacci modulo pe . . . . . . . . . . . . . . . . . . . . . . . 11 11 13
3
. . .
Số không trong dãy Fibonacci modulo m 22 3.1. Ví trí của số không trong dãy Fibonacci modulo m . 22 3.2. Số số không trong một chu kỳ của dãy Fibonacci modulo m 26
Kết luận 34
Tài liệu tham khảo 35
1
Mở đầu
Dãy số Fibonacci được Fibonacci, một nhà toán học người Ý, công bố vào năm 1202 trong cuốn sách Liber Abacci qua hai bài toán: Bài toán con thỏ và Bài toán số các “cụ tổ” của một ong đực. Bài toán con thỏ có thể được phát biểu là: “Một đôi thỏ (gồm một thỏ đực và một thỏ cái) cứ mỗi tháng đẻ được một đôi thỏ con (cũng gồm một thỏ đực và thỏ cái); một đôi thỏ con, khi tròn hai tháng tuổi, sau mỗi tháng đẻ ra một đôi thỏ con, và quá trình sinh nở cứ thế tiếp diễn. Hỏi sau n tháng có bao nhiêu đôi thỏ, nếu đầu năm có một đôi thỏ sơ sinh?”.
Dãy Fibonacci là dãy số tự nhiên thỏa mãn quy tắc Fn+2 = Fn + Fn+1. Tuy đơn giản về quy tắc thiết lập nhưng dãy số Fibonacci chứa đựng vô cùng nhiều những tính chất đẹp đẽ và bất ngờ trong toán học. Nó bí ẩn và lí thú đến mức có hẳn tạp chí The Fibonacci Quarterly hoàn toàn chỉ xuất bản các kết quả nghiên cứu về dãy số này.
Dãy Fibonacci Fn định nghĩa bởi công thức F0 = 0, F1 = 1 và Fn = Fn−1 + Fn−2, với n ≥ 2, là một dãy số quan trọng trong Toán học. Cho m là một số nguyên dương. Xét dãy số Fn modulo m, ký hiệu dãy này là F (mod m). Khi đó dãy này là một dãy tuần hoàn đơn. Ta ký hiệu chu kỳ của dãy F (mod m) là k(m). Chẳng hạn,
F (mod 3) = 0, 1, 1, 2, 0, 1, 1, 2, 0, . . . F (mod 4) = 0, 1, 1, 2, 3, 1, 0, 1, 1, . . . F (mod 5) = 0, 1, 1, 2, 3, 0, 3, 3, 1, 4, 0, 1, 1, . . .
Như vậy k(3) = 4, k(4) = 6 và k(5) = 10.
Mục tiêu của luận văn là tìm hiểu một số tính chất số học thú vị của
hàm k(m) và một số vấn đề liên quan.
Ngoài phần Mở đầu, Kết luận và Tài liệu tham khảo, bố cục của luận
văn được chia làm ba chương.
2
Chương 1. Một số kiến thức chuẩn bị Chương này sẽ dành để giới thiệu ngắn gọn một số thông tin ban đầu và trình bày một số kiến thức về dãy Fibonacci, một số đồng nhất thức liên quan cần thiết cho các chương sau.
Chương 2. Dãy Fibonacci modulo m Chương này trình bày về một số tính chất của chu kỳ k(m) của dãy
Fibonacci modulo m.
Chương 3. Số không trong dãy Fibonacci modulo m Chương này trình bày về ví trí số 0 đầu tiên , cũng như về số số 0
trong một chu kỳ của dãy Fibonacci modulo m.
Luận văn này được hoàn thành dưới sự hướng dẫn của TS. Nguyễn Duy Tân (Viện Toán học - Viện Hàn lâm Khoa học và Công nghệ Việt Nam). Tác giả xin được bày tỏ lòng biết ơn chân thành và sâu sắc tới Thầy hướng dẫn, tới các thầy cô giáo Trường Đại học Khoa học - Đại học Thái Nguyên. Đồng thời tác giả xin gửi lời cảm ơn tới tập thể lớp cao học Toán K12B - Trường Đại học Khoa học đã động viên giúp đỡ trong quá trình học tập và làm luận văn này.
Nhân đây, tôi cũng xin chân thành cảm ơn Khoa Toán - Tin, Phòng Đào tạo trường Đại học Khoa học - Đại học Thái Nguyên đã tạo mọi điều kiện thuận lợi trong quá trình học tập của tôi. Tôi cũng xin được cảm ơn sự nhiệt tình giảng dạy của các giảng viên trong suốt thời gian học tập. Tôi xin cảm ơn Ban giám hiệu Trường
Cuối cùng, tác giả muốn dành những lời cảm ơn đặc biệt nhất đến đại gia đình vì những động viên và chia sẻ những khó khăn để tác giả hoàn thành luận văn này.
Thái Nguyên, ngày 1 tháng 10 năm 2019 Tác giả
Phạm Thị Hồng
3
Chương 1
Một số kiến thức chuẩn bị
Chương này trình bày một số kiến thức chuẩn bị về dãy Fibonacci và sơ lược về thặng dư toàn phương và luật thuận nghịch bậc hai. Tất cả những kết quả trong chương này có thể được tìm thấy trong [1] hoặc [4].
1.1. Dãy Fibonacci
Mặc dù có nhiều đóng góp cho toán học, nhưng ngày nay, Fibonacci được nhớ đến nhờ dãy số nảy sinh từ một vấn đề mà ông đặt ra trong Liber Abaci. Sau đây là một cách diễn đạt:
Một đôi thỏ (gồm một thỏ đực và một thỏ cái) cứ mỗi tháng đẻ được một đôi thỏ con (cũng gồm một thỏ đực và thỏ cái); một đôi thỏ con, khi tròn hai tháng tuổi, sau mỗi tháng đẻ ra một đôi thỏ con, và quá trình sinh nở cứ thế tiếp diễn. Hỏi sau n tháng có bao nhiêu đôi thỏ, nếu đầu năm có một đôi thỏ sơ sinh?
Nếu giả sử rằng cặp đầu tiên không sinh sản cho đến cuối tháng thứ hai, thì trong hai tháng đầu tiên sẽ chỉ có một cặp. Vào đầu tháng thứ ba, cặp đầu tiên sẽ sinh ra một cặp, chúng ta tổng cộng hai cặp. Trong tháng thứ tư, cặp ban đầu lại sinh ra nhưng cặp thứ hai thì không, cho chúng ta ba cặp, v.v.
Giả sử không có con thỏ nào bị chết, chúng ta có thể xác lập một quan hệ truy hồi. Giả sử Fn cặp thỏ trong tháng n, và Fn+1 cặp thỏ trong tháng n + 1. Trong suốt tháng n + 2, tất cả số thỏ từ tháng n + 1 sẽ vẫn giữ nguyên, và những con thỏ đó tồn tại trong tháng thứ n sẽ sinh sản.
4
Do đó
Fn+2 = Fn+1 + Fn.
Dãy số này, với F1 = F2 = 1, được gọi là dãy Fibonacci, và các số hạng trong dãy số này được gọi là các số Fibonacci,
n : 1 2 3 4 5 6 7 8 9 10 11 12 . . . Fn : 1 1 2 3 5 8 13 21 34 55 89 144 . . .
Đến đây, câu trả lời của bài toán Fibonacci là 144. Điều thú vị là mãi đến năm 1634, quan hệ truy hồi phát này mới
được Albert Girard viết ra.
Dãy Fibonacci là dãy số tự nhiên thỏa mãn quy tắc Fn+2 = Fn + Fn+1. Tuy đơn giản về quy tắc thiết lập nhưng dãy số Fibonacci chứa đựng vô cùng nhiều những tính chất đẹp đẽ và bất ngờ trong toán học. Nó bí ẩn và lí thú đến mức có hẳn tạp chí The Fibonacci Quarterly hoàn toàn chỉ xuất bản các kết quả nghiên cứu về dãy số này.
∀n ≥ 0. Dưới đây là một số số hạng đầu tiên của dãy Fibonacci.
Dãy Fibonacci là dãy cho bởi F0 = 0, F1 = 1 và Fn+2 = Fn+1 + Fn,
Fn : 0 1 1 2 3 5 8 13 21 34 55 . . .
Đồng nhất thức 1.1. Fm+n = Fm−1Fn + FmFn+1.
Chứng minh. Ta cố định m, và chứng minh đồng nhất thức trên quy nạp theo n. Với n = 1 thì
Fm+1 = Fm−1 + Fm = Fm−1F1 + FmF2.
Như vậy khẳng định đang cần chứng minh đúng với n = 1.
Giả sử đồng nhất thức đang xét đúng với n = 1, 2, 3, . . . , k. Ta cần
chứng minh rằng nó đúng với n = k + 1. Theo giả thiết quy nạp,
Fm+k = Fm−1Fk + FmFk+1
và
Fm+(k−1) = Fm−1Fk−1 + FmFk.
5
Cộng theo vế hai đẳng thức này ta nhận được
Fm+k + Fm+(k−1) = Fm−1(Fk + Fk−1) + Fm(Fk+1 + Fk).
Suy ra
Fm+(k+1) = Fm−1Fk+1 + FmFk+2,
và do vậy đồng nhất thức đúng với n = k + 1.
Ví dụ, ta có
F12 = F8+4 = F7F4 + F8F5 = 13(3) + 21(5) = 144.
Để thuận tiện, ta mở rộng dãy Fibonacci cho các chỉ số âm bởi công
thức truy hồi, Fn = Fn+2 − Fn+1, n = −1, −2, . . ..
· · · · · ·
· · · −7 − 6 −5 − 4 −3 − 2 −1 0 5 − 3 · · · 1 0
1 2 3 4
13 − 8 2 − 1 1 1 2 3 n : Fn :
Dãy Fibonacci được mở rộng về cả hai phía của trục số như vậy có
thể được gọi là dãy Fibonacci ”song phương". Ta có một đồng nhất thức thú vị sau.
Đồng nhất thức 1.2. F−n = (−1)n+1Fn.
Bây giờ ta kết hợp hai đồng nhất thức trên để nhận được
Đồng nhất thức 1.3. Fm−n = (−1)n(FmFn+1 − Fm+1Fn).
Định lý 1.4. Ta có Fm | Fmn với mọi số nguyên m và n.
Chứng minh. Giả sử m được cố định và ta sẽ thực hiện quy nạp theo n. Nếu m hoặc n bằng không, thì định lý hiển nhiên đúng. Với n = 1 thì rõ ràng Fm | Fm.
Giả sử kết luận của định lý đúng với với n = 1, 2, · · · , k và ta sẽ chứng minh rằng nó đúng với n = k + 1. Sử dụng đồng nhất thức 1.1 ta thấy
Fm(k+1) = Fmk−1Fm + FmkFm+1.
Theo giả thiết quy nạp Fm | Fmk, và do đó Fm chia hết vế phải của đẳng thức trên. Do đó Fm chia hết Fm(k+1). Như vậy định lý được chứng minh
6
cho mọi n ≥ 1. Do Fmn sai khác với F−mn cùng lắm là nhân tử −1, nên ta cũng có Fm | Fmn với n ≤ −1.
n + F2
n+1 = F2n+1.
Đồng nhất thức 1.5. Ta có F2
Chứng minh. Từ đồng nhất thức 1.1, ta có
n+1.
F2n+1 = Fn+(n+1) = Fn−1Fn+1 + FnFn+2 = Fn−1Fn+1 + Fn(Fn + Fn+1) = F2 n + (Fn−1 + Fn)Fn+1 n + F2 = F2
Sau đây là một đồng nhất thức khác chứa bình phương của các số
Fibonacci.
Đồng nhất thức 1.6. Fn+1Fn−1 − F2n = (−1)n.
Chứng minh. Ta có
n−1).
Fn+1Fn−1 − F2n = (Fn−1 + Fn)Fn−1 − F2n = F2 n−1 + Fn(Fn−1 − Fn) = F2 n−1 − FnFn−2 = −(FnFn−2 − F2
−(FnFn−2 − F2n−1) = (−1)2(Fn−1Fn−3 − F2n−2) = (−1)3(Fn−2Fn−4 − F2n−3)
Bây giờ chúng ta có thể lặp lại quá trình trên cho dòng cuối cùng ở trên đây để nhận được
= (−1)n(F1F−1 − F2 0 ) = (−1)n.
...
Phép chứng minh được kết thúc.
7
Nhà lý thuyết số thế kỷ 19 Edouard Lucas là người đầu tiên đặt tên của Fibonacci vào dãy số mà chúng ta đang nghiên cứu. Edouard Lucas cũng khảo sát các tổng quát hóa của dãy số này.
Một dãy Fibonacci tổng quát Gn, là một dãy số xác định bởi quan hệ truy hồi quen thuộc Gn+2 = Gn+1 + Gn nhưng G0 và G1 có thể nhận giá trị bất kỳ. Dãy Lucas, ký hiệu là Ln, là một ví dụ cho dãy Fibonacci tổng quát trong đó L0 = 2 và L1 = 1. Các số tiếp theo là 2, 1, 3, 4, 7, 11, · · ·
Chúng ta sẽ kết thúc mục này bằng hai đồng nhất thức chứa các dãy
Fibonacci tổng quát, xem [4].
Đồng nhất thức 1.7. Ta có Gm+n = Fn−1Gm + FnGm+1.
Chứng minh. Với trường hợp n = 0 và n = 1 ta có
Gm = F−1Gm + F0Gm+1Gm+1 = F0Gm + F1Gm + 1
hai đẳng thức trên là đúng bởi vì F−1 = 1, F0 = 0, và F1 = 1. Cộng hai phương trình ta thấy đồng nhất thức đúng với n = 2, 3, . . . Trừ theo vế của phương trình thứ nhất cho phương trình thứ hai ta nhận được đồng nhất thức đúng với các số n âm. Phép chứng minh được hoàn thành.
Đồng nhất thức 1.8. Ta có Gm−n = (−1)n(FnGm+1 − Fn+1Gm).
Chứng minh. Thay thế −n cho n trong đồng nhất thức trên và sử dụng đồng nhất thức 1.2 ta nhận được điều phải chứng minh.
1.2. Công thức Binet
√
√
5)/2 và β = (1 − 5)/2. Khi đó ta có Công thức Binet
Đặt α = (1 + tính số Fn theo n.
Mệnh đề 1.9. Với mọi n ≥ 0, ta có
, Fn = αn − βn α − β
với mọi n ≥ 0.
Chứng minh. Ta có thể chứng minh công thức này bằng quy nạp theo n. Dễ kiểm tra công thức đúng với n = 0 và n = 1. Giả sử công thức đã
8
(α − β)Fn+1 = (α − β)Fn + (α − β)Fn−1
= αn − βn + αn−1 − βn−1 = αn + αn−1 − (βn + βn−1).
đúng đến n ≥ 1. Ta có
(α − β)Fn+1 = αn+1 − βn+1,
Vì α2 = α + 1, nên αn+1 = αn + αn−1. Tương tự vì β2 = β + 1, nên βn+1 = βn + βn−1. Do vậy
công thức đúng với n + 1.
Đồng nhất thức 1.10. Ta có
+
(cid:19) (cid:19) (cid:19)
5 + 52 + · · · 2n−1Fn = (cid:18)n 1 (cid:18)n 3 (cid:18)n 5
Chứng minh. Ta có
√
√
Fn =
=
(1 +
k
k
=
−
(−1)k
n ∑ k=0 (cid:19)√
3
5
=
+ · · ·
+ 2
(
+
=
αn − βn α − β (cid:16) 1 √ 5)n − (1 − 5)n(cid:17) 2n 5 (cid:35) (cid:19)√ (cid:19)√ 1 √ 5 5 2n 5 (cid:20) (cid:21) (cid:18)n k (cid:19)√ (cid:19)√ 1 √ 5 + 2 5 5 (cid:18)n k (cid:18)n 5 5 (cid:34) n ∑ k=0 (cid:18)n 1 (cid:19) (cid:19) (cid:19)
5 + 52 + · · · ). 2 (cid:18)n 1 (cid:18)n 3 (cid:18)n 3 (cid:18)n 5 2n 1 2n−1
Từ đó ta có điều phải chứng minh.
1.3. Luật thuận nghịch bậc hai
Định nghĩa 1.11. Cho p là một số nguyên tố và a là một số nguyên sao cho p (cid:45) a. Số a được gọi là một thặng dư toàn phương modulo p nếu tồn
9
tại một số nguyên y sao cho y2 ≡ a(mod p). Nếu không tồn tại một số nguyên y nào sao cho y2 ≡ a(mod p) thì ta nói a là phi thặng dư toàn phương modulo p.
Ví dụ. Các số 1, 2, 4 là các thặng dư bậc hai modulo 5, trong khi đó 2 là không thặng dư bậc hai modulo 5 vì phương trình y2 ≡ 2(mod5) vô nghiệm.
dư toàn phương) modulo p nếu và chỉ nếu a Định lý 1.12 (Tiêu chuẩn Euler). Cho p là một số nguyên tố lẻ không là ước của số nguyên a. Khi đó a là một thặng dư toàn phương (tương ứng, phi thặng p−1 2 ≡ 1(mod p) (tương ứng,
p−1 2 ≡ −1(mod p)).
a
=
−1 nếu a không là thặng dư toàn phương modulo p
Định nghĩa 1.13 (Ký hiệu Legendre). Cho p là một số nguyên tố lẻ không chia hết số nguyên a. (cid:19) (cid:26) 1 nếu a là thặng dư toàn phương modulo p Ta định nghĩa: (cid:18) a p
Ký hiệu này được gọi là ký hiệu Legendre.
(cid:19)
1.
=
(cid:19) (cid:19)
≡ a
2. . (cid:19) (cid:18) b p
=
3. (cid:18) a2 p (cid:18) ab p (cid:18) a (cid:19) p (cid:19) (cid:19)
4. Nếu a ≡ b (mod p) thì . Một số tính chất Cho p là số nguyên tố lẻ không chia hết các số nguyên a và b. Khi đó ta có các tính chất sau. = 1. (cid:18) a p p−1 2 (mod p) (Tiêu chuẩn Euler). (cid:18) a p (cid:18) b p (cid:19)
=
5. (cid:18) −1 p (cid:19)
= 1 và nếu p ≡ 1 (mod8) hoặc p ≡ 7 (mod8); và
6. Khi đó bằng 1 hoặc −1 tùy theo p ≡ 1 (mod4) hay p ≡ 3 (mod4). (cid:19) (cid:18) 2 (cid:18) 2 p p
1 nếu p ≡ 3 (mod8) hoặc p ≡ 5 (mod8).
= −
=
(cid:19) (cid:19) (cid:19) (cid:19)
. ; và nếu p ≡ q ≡ 3 (mod4) thì Định lý 1.14 (Luật thuận nghịch bậc hai Gauss). Giả sử p và q là các số nguyên tố lẻ phân biệt. Khi đó nếu p ≡ 1 (mod 4) hoặc q ≡ 1 (mod 4) thì (cid:18) p q (cid:18) q p (cid:18) p q (cid:18) q p
10
Ở chương sau, chúng ta sẽ sử dụng bổ đề sau đây.
Bổ đề 1.15. Cho p là một số nguyên tố. Khi đó nếu p có dạng 5t ± 1 thì 5 là thặng dư toàn phương modulo p; nếu p có dạng 5t ± 2 thì 5 là phi thặng dư toàn phương modulo p.
=
(cid:19) (cid:17) Chứng minh. Theo Luật thuận nghịch bậc hai ta có do 5 là (cid:18) 5 p (cid:16) p 5
một số nguyên tố có dạng 4t + 1. Ta có
=
=
= 1,
(cid:19) (cid:19) (cid:19) (cid:18) 5
=
=
= 1.
5t + 1 (cid:19) (cid:19) (cid:19) (cid:18) 5
5t − 1 (cid:18)5t + 1 5 (cid:18)5t − 1 5 (cid:18)1 5 (cid:18)4 5
Ta cũng có
=
=
= −1,
(cid:19) (cid:19) (cid:19) (cid:18) 5
) =
=
= −1.
5t + 2 (cid:19) (cid:19) (cid:19) (cid:18) 5
5t − 2 (cid:18)5t + 2 5 (cid:18)5t − 2 5 (cid:18)2 5 (cid:18)3 5
Ta có điều phải chứng minh.
11
Chương 2
Chu kỳ của dãy Fibonacci mod m
Ta có thể tìm hiểu dãy Fibonacci bằng cách xét dãy các số dư của các số Fibonacci theo một modulo m cho trước. Một trong những nghiên cứu hiện đại đầu tiên về lĩnh vực này được thực hiện bởi D. D. Wall [6] vào năm 1960, mặc dù J. L. Lagrange đã thực hiện một số nghiên cứu về các dãy kiểu này trong thế kỷ XVIII. Chương này trình bày về chu kỳ của dãy Fibonacci mod m. Tài liệu tham khảo cho chương này là [6] và [3].
2.1. Một số tính chất cơ bản
Đầu tiên ta có thể quan sát rằng, dãy Fibonacci mod m là tuần hoàn. Chẳng hạn,
F (mod 4) = 0 1 1 2 3 1 0 1 1 2 3 . . . F (mod 5) = 0 1 1 2 3 0 3 3 1 4 0 4 4 3 2 0 2 2 4 1 0 1 1 2 3 . . .
Tổng quát hơn, ta có thể chứng minh rằng với dãy Fibonacci tổng
quát G, thì dãy G modulo m là dãy tuần hoàn đơn.
Mệnh đề 2.1. Dãy G (mod m) là dãy tuần hoàn đơn, tức là dãy này lặp lại từ giá trị đầu tiên.
Chứng minh. Ta xét các cặp (Gn mod m, Gn+1 mod m) với n = 0, 1, 2, . . .. Chỉ có hữu hạn m2 cặp phân biệt như vậy. Do đó tồn tại 0 ≤ s < t sao
12
(Gs mod m, Gs+1 mod m) = (Gt mod m, Gt+1 mod m).
cho
Vì Gn+1 = Gn + Gn−1, nên Gn−1 = Gn+1 − Gn. Ta suy ra
Gs−1 = Fs+1 − Gs ≡ Gt+1 − Gt = Gt−1 mod m.
(Gs−1 mod m, Gs mod m) = (Gt−1 mod m, Gt mod m).
Do vậy
(G0 mod m, G1 mod m) = (Gt−s mod m, Gt−s+1 mod m).
Tiếp tục quá trình này ta suy ra
Đặt k = t − s. Khi đó Gk ≡ G0 mod m và Gk+1 ≡ G1 mod m. Từ đó ta suy ra dãy G (mod m) là tuần hoàn đơn.
Định nghĩa 2.2. (a) Cho dãy Fibonacci tổng quát Gn định nghĩa bởi G0 = a, G1 = b và Gn+1 = Gn + Gn−1, n = 1, 2, . . .. Ta gọi hG(m) hoặc viết đơn giản là h(m), là chu kỳ của dãy tuần hoàn đơn G (mod m).
(b) Ta gọi k(m) là chu kỳ của dãy tuần hoàn đơn F (mod m).
Định lý 2.3. Với m ≥ 3, k(m) là số chẵn.
Chứng minh. Để ngắn gọn, ta ký hiệu k = k(m). Khi đó Fk ≡ F0 = 0 (mod m), Fk+1 ≡ F1 = 1 (mod m) và Fk−1 = F−1 = 1 (mod m). Từ đồng nhất thức
k = (−1)k,
Fk+1Fk−1 − F2
ta suy ra (−1)k ≡ 1 × 1 − 02 = 1 (mod m). Vì m ≥ 3, nên (−1)k = 1 và do đó k chẵn.
Một tính chất thú vị của F (mod m) là k(n) | k(m) khi mà n | m. Đáng ngạc nhiên, tính chất này cũng đúng với dãy Fibonacci tổng quát.
Định lý 2.4. Cho (Gn) là dãy một Fibonacci tổng quát và gọi h = hG. Khi đó ta có các khẳng định sau.
(i) Nếu n | m, thì h(n) | h(m).
13
i thì h(m) = lcm[h(pei
i )],
(ii) Nếu m có phân tích ra thừa số nguyên tố m = ∏ pei
i ).
bội chung nhỏ nhất của h(pei
(iii) Ta có h([m, n]) = [h(m), h(n)], trong đó các dấu ngoặc là ký hiệu cho hàm
bội chung nhỏ nhất.
Chứng minh. (i) Ta đặt h = h(m). Với mọi i, ta có Gi ≡ Gi+h (mod m). Vì n là ước của m nên ta có Gi ≡ Gi+h (mod n). Tức là G (mod n) lặp lại theo các khối độ dài h. Điều này suy ra h(n) là ước của h.
i ) | h(m) với mọi i. Do vậy
i )] Theo (i), ta có h(pei
(ii) Đặt h := lcm[h(pei
h | h(m).
i ) | h nên G (mod pei i ) lặp lại theo các khối có độ dài h. Do đó i ) với mọi i. Vì các pei Gh ≡ G0 và Gh+1 ≡ G1 (mod pei là nguyên tố cùng i nhau, nên ta suy ra rằng Gh ≡ G0 (mod m) và Gh+1 ≡ G1 (mod m). Do đó G (mod m) lặp lại theo các khối có độ dài h và ta có h(m) | h. Như vậy h = h(m).
Vì h(pei
[m, n] và n |
[m, n], ta có h(m) | h([m, n]) và h(n) | h([m, n]). Suy ra [h(m), h(n)] | h([m, n]). Giả sử ta có phân tích nguyên tố [m, n] = pe1
t . Khi đó
1 . . . pet
(iii) Do m |
t )].
t ) = [h(pe1
1 . . . h(pet
1 . . . pet
i ) chia hết h(m) hoặc h(n) với t )] | [h(m), h(n)]. Nói cách khác, h([m, n]) |
i chia hết m hoặc n với mọi i, nên h(pei Vì pei mọi i. Do đó [h(pei i ) . . . h(pet [h(m), h(n)]. Do đó h([m, n]) = [h(m), h(n)].
h([m, n]) = h(pe1
2.2. Chu kỳ của dãy Fibonacci modulo pe
Theo kết quả ở mục trước, bài toán mô tả k(m) đưa về mô tả k(pe). Trước tiên chúng ta sẽ xét trường hợp riêng cho k(2e).
Bổ đề 2.5. Với mọi r ≥ 3, ta có
(mod 2r) và F3·2r−2+1 ≡ 2r−1 + 1 (mod 2r).
F3·2r−2 ≡ 0
Chứng minh. Ta chứng minh quy nạp theo r. Kiểm tra trực tiếp cho r = 3, ta thấy khẳng định là đúng: F6 = 8 ≡ 0 (mod 23) và F7 = 13 ≡ 22 + 1 (mod 23). Giả sử bổ đề đúng với r.
14
Ta có
F3·2r−1 = (F3·2r−2)(F3·2r−2−1 + F3·2r−2+1). Theo giả thuyết quy nạp, F3·2r−1 ≡ 0 (mod 2r). Dễ thấy mỗi số Fn là chẵn nếu 3 | n và Fn là lẻ nếu 3 (cid:45) n. Do vậy F3·2r−1−1 + F3·2r−1+1 ≡ 0 (mod 2). Do đó, F3·2r−1 ≡ 0 (mod 2r). Ta có
F3·2r−1+1 = (F3·2r−2+1)2 + (F3·2r−2)2. Ta xét số hạng đầu tiên ở vế phải. Vì F3·2r−2+1 ≡ 2r−1 + 1 (mod 2r) nên
F3·2r−2+1 ≡ (2r−1 + 1) hoặc (2r−1 + 1 + 2r) (mod 2r+1).
(2r−1 + 1)2 = 22r−2 + 2r + 1 ≡ 2r + 1 (mod 2r+1)
(2r−1 + 1 + 2r)2 = (3 · 2r−1 + 1)2
= 9 · 22r−2 + 3 · 2r + 1 ≡ 2r + 1 (mod 2r+1).
Ta có
(F3·2r−2+1)2 ≡ 2r + 1 (mod 2r+1). Bây giờ ta xét số hạng thứ hai ở vế phải. Vì F3·2r−2 ≡ 0 (mod 2r), nên
Do vậy
F3·2r−2 ≡ 0 hoặc 2r (mod 2r+1),
(F3·2r−2)2 ≡ 0 (mod 2r+1).
Ta có (2r)2 = 22r ≡ 0 (mod 2r+1). Do đó
Như vậy F3·2r−1+1 ≡ 2r + 1 (mod 2r+1), và ta có điều phải chứng minh.
Định lý 2.6. Ta có k(2e) = 3 · 2e−1.
Chứng minh. Ta chứng minh quy nạp theo e. Kiểm tra trực tiếp, ta có k(2) = 3 và k(4) = 6, và định lý đúng với với e = 1, 2. Giả sử ta có k(2e) = 3 · 2e−1.
Từ bổ đề trên ta suy ra F3·2e ≡ 0 (mod 2e+1) và F3·2e+1 ≡ 2e+1 + 1 ≡ 1 (mod 2e+1). Do đó k(2e+1) | 3 · 2e. Mặt khác k(2e) | k(2e+1). Do vậy
15
k(2e+1) = 3 · 2e−1 hoặc 3 · 2e. Nhưng theo bổ đề trên F3·2e−1+1 ≡ 2e + 1 (cid:54)= 1 (mod 2)e+1. Ta suy ra k(2e+1) (cid:54)= 3 · 2e−1 và do đó k(2e+1) = 3 · 2e, ta có điều phải chứng minh.
Bây giờ ta sẽ nghiên cứu giá trị k(pe) với p nguyên tố lẻ. Ta sẽ làm
việc với ma trận U được định nghĩa bởi
(cid:21) U = . (cid:20)0 1 1 1
Ta gọi M2(Z) là tập các ma trận cỡ 2 × 2 hệ số nguyên. Ta nói hai ma trận A = [aij] và B = [bij] thuộc M2(Z) là đồng dư với nhau modulo m, và viết A ≡ B (mod m), nếu aij ≡ bij (mod m) với mọi i, j. Ta cũng nói m chia hết ma trận A, viết m | A, nếu m | aij, với mọi i, j. Ta cũng ký hiệu (cid:21) I = , ma trận đơn vị cỡ 2 × 2. (cid:20)1 0 0 1
(cid:21)
(i) Với mọi n ≥ 1, ta có Un = . Bổ đề 2.7. Các khẳng định sau là đúng. (cid:20)Fn−1 Fn Fn Fn+1
(ii) Với m ≥ 2, ta có Uk(m) = I + mB ≡ I (mod m), với B ∈ M2(Z) nào
đó.
(iii) Nếu Un ≡ I (mod m), thì k(m) | n.
Chứng minh. (i) Ta chứng minh quy nạp theo n. Hiển nhiên công thức đúng với n = 1. Ta giả sử công thức đã đúng với n. Ta có
·
(cid:21) (cid:21) Un+1 = Un · U = (cid:20)0 1 1 1
=
=
Fn Fn+1 (cid:21) (cid:21)
. (cid:20)Fn−1 Fn (cid:20) Fn Fn−1 + Fn Fn+1 Fn + Fn+1 (cid:20) Fn Fn+1 Fn+1 Fn+2
Do vậy công thức cũng đúng với n + 1.
(ii) Từ phần (i) ta suy ra
≡
= I
(mod m).
(cid:34) (cid:35) (cid:21) Uk(m) = (cid:20)F−1 F0 F0 F1 Fk(m)−1 Fk(m) Fk(m) Fk(m)+1
16
Do vậy Uk(m) = I + mB với B ∈ M2(Z).
(mod m).
(iii) Giả sử Un ≡ I (mod m). Khi đó, từ phần 1 ta suy ra
(mod m) và Fn+1 ≡ 1
Fn ≡ 0
Do đó k(m) | n.
Định lý 2.8. Gọi t là số nguyên lớn nhất sao cho k(pt) = k(p). Khi đó k(pe) = pe−tk(p) với mọi e ≥ t.
Chứng minh. Với p = 2, ta có k(4) = 6 > k(2) = 3 và k(2e) = 2e−1 · 3. Định lý đúng với p = 2.
Bây giờ ta xét trường hợp p > 2. Ta có Uk(pe) = I + peB, với B ∈
M2(Z) nào đó. Suy ra
= I p +
i ), với mọi i = 1, . . . , p − 1 (chú ý rằng p lẻ). Do vậy U pk(pe) ≡ Vì p | (p I (mod pe+1). Theo bổ đề trên, ta suy ra k(pe+1) | pk(pe). Mặt khác, ta đã biết k(pe) | k(pe + 1), và do đó k(pe+1) bằng k(pe) hoặc pk(pe).
U pk(pe) = (I + peB)p (cid:19) (cid:19) I p−1(peB) + I p−2(peB)2 + · · · (cid:18)p 1 (cid:18)p 2
Bây giờ ta giả sử k(pe+1) = pk(pe) và ta sẽ chứng minh k(pe+2) =
pk(pe+1).
Vì k(pe) < k(pe+1), nên ta có Uk(pe) = I + peB với p (cid:45) B. Do đó
= I p +
U pk(pe) = (I + peB)p (cid:19) (cid:19) I p−1(peB) + I p−2(peB)2 + · · · (cid:18)p 1
(cid:18)p 2 ≡ I + pe+1B (mod pe+2).
Do đó
Uk(pe+1) = U pk(pe) ≡ I + pe+1B (cid:54)≡ I (mod pe+2).
Điều này kéo theo k(pe+1) (cid:54)= k(pe+2), và ta có k(pe+2) = pk(pe+1).
Bâu giờ giả sử t là số lớn nhất e sao cho k(pe) = k(p). Khi đó theo những lập luận ở trên, ta có k(pe) = k(p) với 1 ≤ e ≤ t và k(pe) = k(pe−t) với e ≥ t.
17
Có một giả thuyết (đề cập trong bài báo của Wall năm 1960), nói rằng số t trong định lý trên luôn là 1, tức là ta luôn có k(p) < k(p2). Giả thuyết này hiện nay vẫn còn là mở.
Tính toán k(p) theo p là khó, và phần tiếp theo chúng ta sẽ đưa ra
một số chặn trên của k(p).
Chúng ta sẽ sử dụng ba tính chất sau với mọi số nguyên tố p.
Bổ đề 2.9. Cho p là một số nguyên tố. Khi đó
(p n) ≡ 0 (mod p) với 1 ≤ n ≤ p − 1. (p−1
(1)
n ) ≡ (−1)n (mod p) với 0 ≤ n ≤ p − 1.
(p+1
(2)
n ) ≡ 0 (mod p) với 2 ≤ n ≤ p − 1.
(3)
n) =
) ≡ (−1) (mod p). Do vậy
Chứng minh. (1) Xét 1 ≤ n ≤ p − 1. Đăt a := (p . Khi đó p! n!(p − n)!
n!(p − n)!a = p! chia hết cho p. Vì n! và (p − n)! đều không chia hết cho p, nên a chia hết cho p. (2) Ta có (p−1 1
=
−
≡ −(−1) = (−1)2
(mod p).
(cid:19) (cid:19) (cid:19)
(cid:18)p − 1 2 (cid:18)p 2 (cid:18)b − 1 1
n ) ≡ (−1)n (mod p).
Chứng minh bằng quy nạp ta có (p−1
(3) Với 2 ≤ n ≤ p − 1, ta có
=
+
≡ 0
(mod p).
(cid:19) (cid:19) (cid:19) (cid:18) p
(cid:18)p + 1 n (cid:18)p n n − 1
Định lý 2.10. Nếu số nguyên tố p có dạng 5t ± 1 thì Fp−1 ≡ 0 và Fp ≡ 1 (mod p). Nếu số nguyên tố p có dạng 5t ± 2 thì Fp ≡ −1 và Fp+1 ≡ 0 (mod p).
Chứng minh. Ta có
+
(cid:19) (cid:19) (cid:19)
p−1 2 .
5 + · · · + 5 2p−1Fp = (cid:18)p p (cid:18)p 3 (cid:18)p 1
18
p−1 2 (mod p). Từ Bổ đề 1.15 và tiêu chuẩn Euler, ta có 5
Áp dụng (1) trong bổ đề trên và Định lý Fermat nhỏ ta suy ra Fp ≡ p−1 2 ≡ 1 (mod p) 5 p−1 nếu và chỉ nếu p = 5t ± 1, và 5 2 ≡ −1 (mod p) nếu và chỉ nếu p = 5t ± 2. Do đó,
Nếu một số nguyên tố p có dạng 5t ± 1 thì Fp ≡ 1 (mod p); Nếu một số nguyên tố p có dạng 5t ± 2 thì Fp ≡ −1 (mod p).
Ta có
+
(cid:19) (cid:19) (cid:19)
p−3 2 .
5 + · · · + 5 2p−2Fp−1 = (cid:18)p − 1 1 (cid:18)p − 1 3 (cid:18)p − 1 p − 2
Từ (2) trong bổ đề trên, ta suy ra
p−3 2 ) = −
(mod p).
p−1 2 − 1 4
5 2p−2Fp−1 ≡ −(1 + 5 + 52 + · · · + 5
p−1 2 ≡
(cid:19)
= 1 (mod p). Khi đó 2p−2Fp−1 ≡
Nếu p = 5t ± 1, thì 5 (cid:18) 5 p
0 (mod p), và do vậy Fp−1 ≡ 0 (mod p).
Giả sử p = 5t ± 2. Ta có
+
(cid:19) (cid:19) (cid:19)
p−1 2 .
5 + · · · + 5 2pFp+1 = (cid:18)p + 1 p (cid:18)p + 1 1 (cid:18)p + 1 3
Từ (3) trong bổ đề trên, ta suy ra
p−1 2
+
p−1 2 = (p + 1) + (p + 1)5
(cid:19) (cid:19)
≡ 1 + 5
p−1 2 ≡ 0 (mod p).
5 2pFp+1 ≡ (cid:18)p + 1 p (cid:18)p + 1 1
Do đó Fp+1 ≡ 0 (mod p). Phép chứng minh được hoàn thành.
Định lý 2.11. Cho p là một số nguyên tố, p (cid:54)= 5. Khi đó ta có các khẳng định sau.
(i) Ta có k(p) | p2 − 1.
19
(ii) Nếu số nguyên tố p có dạng 5t ± 1 thì k(p) | p − 1.
(iii) Nếu số nguyên tố p có dạng 5t ± 2 thì k(p) | 2p + 2.
Chứng minh. (i) Ta có k(2) = 3, và định lý đúng với p = 2. Bây giờ ta giả sử p lẻ. Để chứng minh (i) ta sẽ chứng minh rằng Fp2−1 ≡ 0 và Fp2 ≡ 1 (mod p).
Nếu p = 5t ± 1 thì p | Fp−1. Ta có p − 1 | p2 − 1 và do đó Fp−1 | Fp2−1. Vì thế p | Fp2−1. Nếu p = 5t ± 2 thì p | Fp+1. Ta có p + 1 | p2 − 1 và vì vậy Fp+1 | F2 p − 1. Do đó p | Fp2−1. Do vậy với mọi p (cid:54)= 5, Fp2−1 ≡ 0 (mod p).
Để chứng minh Fp2 ≡ 1 (mod p), đầu tiên ta chú ý rằng
p2−1 2
+
(cid:19) (cid:19) (cid:19)
n ) ≡ 0 (mod p) với 1 ≤
5 + · · · + . 5 2p2−1Fp2 = (cid:18)p2 p2 (cid:18)p2 1 (cid:18)p2 3
p2−1 2 = (5
p−1 2 )p+1 ≡ (±1)p+1 ≡ 1 (mod p).
Bây giờ 2p2−1 = (2p−1)p+1 ≡ 1 (mod p) và (p2 n ≤ p2 − 1. Do đó
F2 p ≡ 5
Vì vậy phép chứng minh của định lý được hoàn thành.
(ii) Do p = 5t ± 1, Định lý 2.10 nói rằng Fp−1 ≡ 0 và Fp ≡ 1 (mod p). Do đó F (mod p) lặp lại trong các khối có độ dài p − 1. Vì vậy k(p) | p − 1.
(iii) Giả sử p = 5t ± 2. Theo Định lý 2.10 thì, Fp+1 ≡ 0 (mod p). Vì
p + 1 | 2p + 2, nên Fp+1 | F2p+2. Do đó F2p+2 ≡ 0 (mod p).
Ta có Fp+2 = Fp+1 + Fp ≡ 0 + (−1) = −1 (mod p) và Fp+3 = Fp+2 +
Fp+1 ≡ (−1) + 0 = −1 (mod p). Từ đó ta suy ra
≡ (−1)(−1) + (0)(−1) ≡ 1 (mod p).
F2p+3 = F(p+1)+(p+2) = FpFp+2 + Fp+1Fp+3
Như vậy k(p) | 2p + 2.
Trong phần cuối của mục này chúng ta trình bày một số kết quả của
D.D. Wall về mối quan hệ giữa h(m) và k(m).
20
Mệnh đề 2.12. Ta có h(m) | k(m).
Chứng minh. Để đơn giản, ta viết k = k(m). Áp dụng đồng nhất thức (1.7) ta nhận được
Gk = Fk−1G0 + FkG1 ≡ G0 (mod m)
và
Gk+1 = FkG0 + Fk+1G1 ≡ G1 (mod m).
Do đó G (mod m) lặp lại theo các khối có độ dài k = k(m). Từ đây ta có h(m) | k(m).
Định lý 2.13. Nếu một số nguyên tố p có dạng 5t ± 2 thì h(pe) = k(pe). Ở đây h(pe) là chu kỳ modulo pe của dãy Fibonacci tổng quát Gn với gcd(G0, G1, p) = 1.
Chứng minh. Để đơn giản, ta đặt h = h(pe). Ta có
Gh − G0 ≡ 0 (mod pe), G1 − G1 ≡ 0 (mod pe).
(Fh−1G0 + FhG1) − G0 = G1Fh + G0(Fh−1 − 1) ≡ 0 (mod p), (Fh−1G1 + Fh+1G2) − G1 = G2Fh + G1(Fh−1 − 1) ≡ 0 (mod p).
Từ đồng nhất thức (1.7), ta suy ra
Bây giờ ta xem hai đẳng thức trên như một hệ phương trình với ma 1 − G0G2. Ta sẽ chứng minh D (cid:54)≡ 0 trân hệ số có định thức D = G2 (mod p).
Giả sử rằng D ≡ 0 (mod p). Khi đó p (cid:45) G1. Thật vậy, giả sử p | G1. Ta suy ra p | G0G2. Nếu p | G2 thì p | G0 = G2 − G1. Ta luôn có p | G0, trái giả thiết về dãy Gn.
Ta có
2 ≡ 0 (mod p).
2 − G0(G0 + G1) 2 − G0G1 − G0
2 − G0G2 = G1 = G1
G1
21
2 ≡ 0 (mod p).
Nhân cả hai vế với −4. Ta nhận được
2 + 4G0G1 − 4G1
2 vào hai vế,
4G0
2 (mod p).
Cộng 5G1
2 + 4G0G1 + G1
2 = (2G0 + G1)2 ≡ 5G1
4G0
Vì G1 (cid:54)= 0 (mod p), nên ta suy ra 5 là một thặng dư toàn phương modulo p. Tuy nhiên, theo Bổ đề 1.15, điều này mâu thuẫn với giả thiết của chúng ta là p = 5t ± 2.
Như vậy D (cid:54)≡ 0 (mod p), và do đó D (cid:54)≡ 0 (mod pe). Do định thức của ma trận đang xét không đồng dư với không theo modulo pe, nó phải có nghiệm duy nhất theo modulo pe. Rõ ràng Fh ≡ 0 và (Fh−1 − 1) ≡ 0 (mod pe)) thỏa mãn hệ phương trình, và do đó Fh ≡ 0 và Fh−1 ≡ 1 (mod pe). Từ quan hệ truy hồi, ta suy ra Fh+1 ≡ 1 (mod pe). Từ đây ta có k(pe) | h = h(pe). Theo Định lý 2.12 ta có h(pe) | k(pe). Do đó h(pe) = k(pe).
22
Chương 3
Số không trong dãy Fibonacci modulo m
Chương này trình bày về vị trí của số 0 trong dãy Fibonacci modulo m, cũng như số số 0 trong một chu kỳ của dãy Fibonacci modulo m. Tài liệu sử dụng cho chương này [3], [2], [5].
3.1. Ví trí của số không trong dãy Fibonacci modulo m
Cho m là số nguyên dương. Ta gọi α(m) là chỉ số của số hạng dương đầu tiên của dãy Fibonacci mà là ước của m, tức là α(m) là số nguyên dương nhỏ nhất k sao cho Fk chia hết cho m. Ví dụ α(2) = 3, α(3) = 4.
Bổ đề 3.1. Với số nguyên dương n cho trước, m | Fn khi và chỉ khi α(m) | n. Nói riêng, ta có α(m) | k(m).
Chứng minh. Đặt a = α(m). Giả sử a | n. Theo Định lý 1.4, ta có Fa | Fn. Vì Fa ≡ 0 (mod m), tức là m | Fa, nên m | Fn.
(mod m),
Ngược lại ta giả sử m | Fn. Bằng cách chia n cho a ta có thể viết n = ka + r, với 0 ≤ r < a. Theo phần trên Fka ≡ 0 (mod p). Do vậy Fka−1 (cid:54)= 0 (mod m), vì nếu không, dùng quan hệ truy hồi ta suy ra Fl ≡ 0 (mod m), với mọi l, vô lý. Vì
0 ≡ Fn = Fka+r = Fka−1Fr + FkaFr+1 ≡ Fka−1Fr
23
và m (cid:45) Fka−1, nên Fr ≡ 0 (mod m). Nhưng vì r < a = α(m), nên ta suy ra r = 0 và a | n.
Hàm α(m) có một số tính chất giống như k(m).
Mệnh đề 3.2. Ta có các khẳng định sau.
(i) Nếu n | m thì α(n) | α(m).
i thì α(m) = lcm[α(pei
i )].
(ii) Nếu m có phân tích nguyên tố m = ∏ pei
(iii) Ta có α([m, n]) = [α(m), α(n)].
Chứng minh. (i) Ta có m | Fα(m). Do đó n | Fα(m) và ta có α(n) | α(m).
(ii) Chú ý rằng
⇐⇒ α(pei
với mọi i m | Fn ⇐⇒ pei i
| Fn i ) | n
với mọi i.
i )].
Số n nhỏ nhất thỏa mãn điều kiện cuối cùng là n = lcm[α(pei i )]. Do đó theo điều kiện đầu tiên, Fn là số Fibonacci nhỏ nhất chia hết cho m. Nói cách khác α(m) = n = lcm[α(pei
(iii) Ta có
⇐⇒ α(m) | t
Ft ≡ 0 (mod [m, n]) ⇐⇒ Ft ≡ 0 (mod m) Ft ≡ 0 (mod n)
và và α(n) | t.
Số t nhỏ nhất mà điều kiện thứ nhất xảy ra là t = α([m, n]). Số t nhỏ nhất mà điều kiện cuối cùng đúng là t = [α(m), α(n)]. Phép chứng minh được hoàn thành.
Định nghĩa 3.3. (a) Ta gọi s(m) là số dư của Fα(m)+1 modulo m.
(b) Ta gọi β(m) là bậc của của s(m) modulo m. (Nhắc lại rằng điều này có nghĩa là s(m)β(m) ≡ 1 (mod m), và nếu 1 ≤ n < β(m) thì s(m)n (cid:54)≡ 1 (mod m).)
Ví dụ 3.4. Với m = 2, dãy Fibonacci modulo 2 là
0 1 1 0 1 1 0 1 · · ·
và α(2) = 3, s(2) = 1, β(2) = 1, k(2) = 3.
24
Với m = 3, dãy Fibonacci modulo 3 là
0 1 1 2 0 2 2 1 0 1 1 2 · · ·
và α(3) = 4, s(2) = 2, β(3) = 2, k(3) = 8. Với m = 4, dãy Fibonacci modulo 4 là
0 1 1 2 3 1 0 1 1 · · ·
và α(4) = 6, s(4) = 1, β(4) = 1, k(4) = 6. Với m = 5, dãy Fibonacci modulo 5 là
0 1 1 2 3 0 3 3 1 4 0 4 4 3 2 0 2 2 4 1 0 1 1 · · ·
và α(5) = 5, s(5) = 3, β(5) = 4, k(5) = 10. Với m = 6, dãy Fibonacci modulo 6 là
0 1 1 2 3 5 2 1 3 4 1 5 0 5 5 4 3 1 4 5 3 2 5 1 0 1 1 · · ·
và α(6) = 12, s(6) = 5, β(6) = 2, k(5) = 24. Với m = 7, dãy Fibonacci modulo 7 là
0 1 1 2 3 5 1 6 0 6 6 5 4 2 6 1 0 1 1 · · ·
và α(7) = 8, s(7) = 6, β(7) = 2, k(7) = 16. Với m = 8, dãy Fibonacci modulo 8 là
0 1 1 2 3 5 0 5 5 2 7 1 0 1 1 · · ·
và α(8) = 6, s(8) = 5, β(8) = 2, k(8) = 12. Với m = 9, dãy Fibonacci modulo 9 là
0 1 1 2 3 5 8 4 3 7 1 8 0 8 8 7 6 4 1 5 6 2 8 1 0 1 1 · · ·
và α(9) = 12, s(9) = 8, β(9) = 2, k(9) = 24.
25
Với m = 10, dãy Fibonacci modulo 10 là
0 1 1 2 3 5 8 3 1 4 5 9 4 3 7
0 7 7 4 1 5 6 1 7 8 5 3 8 1 9
0 9 9 8 7 5 2 7 9 6 5 1 6 7 3
0 3 3 6 9 5 4 9 3 2 5 7 2 9 1 0 1 1 · · ·
và α(10) = 15, s(10) = 7, β(10) = 4, k(10) = 60.
Định lý 3.5. k(m) = α(m)β(m).
· · ·
Chứng minh. Giả sử một chu kỳ đơn của F (mod m) được phân chia thành các phần nhỏ hơn, các dãy con hữu hạn A0, A1, A2, . . . như dưới đây
0 1. (3.1) 0 s3
0 1 · · · s1 (cid:123)(cid:122) (cid:125) (cid:124) A0 0 s2 · · · s3 (cid:123)(cid:122) (cid:125) (cid:124) A1 0 s1 · · · s2 (cid:123)(cid:122) (cid:125) (cid:124) A1
Trong mỗi dãy con Ai, có α(m) số hạng, nó chứa đúng một số 0, và s1 = s(m).
Mỗi dãy con Ai với i ≥ 1 là một bội của A0. Chính xác hơn, ta có các
đồng dư sau modulo m.
A1 ≡ s1A0 A2 ≡ s2A0
...
An−1 ≡ sn−1A0 An ≡ sn A0
...
Số hạng cuối cùng trong An−1 là sn, và số hạng cuối cùng trong A0 là s1. Do đó
≡ (sn−2) · s1 · s1 ≡ (sn−3) · s1 · s1 · s1
sn ≡ (sn−1) · s1
...
26
≡ sn 1
· · · 0 1.
với các đồng dư modulo m. Do β(m) là bậc của s1, dãy (3.1) có thể được viết lại dưới dạng
1 · · · 0 s3
1 · · · · · · · · · 0 sβ(m)−1
1
0 1 · · · 0 s1 · · · 0 s2
Do đó β(m) có thể được hiểu theo một cách khác: nó là số các số không trong một chu kỳ đơn của F (mod m). Do vậy k(m) = α(m)β(m).
· Fr (mod m).
Từ phép chứng minh trên ta nhận được đồng nhất thức.
α(m)+1
1 Fr ≡ Fn
α(m)+1
Đồng nhất thức 3.6. Fn·α(m)+r ≡ Fn
Chứng minh. Đồng nhất thức nhận được từ đồng dư An ≡ sn 1 A0. Với 0 ≤ r < α(m), ta có số hạng thứ r của An là đồng dư với sn 1 lần số hạng thứ r của A0 modulo m. Do đó Fnα(m)+r ≡ sn · Fr (mod m). Như vậy đẳng thức đúng với 0 ≤ rα(m). Bằng phép quy nạp tiến ta thấy, đẳng thức đồng dư đúng với mọi r nguyên không âm, và bằng cách quy nạp lùi ta thấy đẳng thức đồng dư cũng đúng với r nguyên âm.
3.2. Số số không trong một chu kỳ của dãy Fibonacci mod-
ulo m
Định lý sau đây nói rằng số số không β(m) trong một chu kỳ của dãy Fibonacci modulo m là 1,2 hoặc 4.
Định lý 3.7. Ta có β(m) = 1, 2 hoặc 4.
n − Fn+1Fn−1 = (−1)n+1, với mọi n. Nói riêng,
Chứng minh. Ta có F2
α(m) − Fα(m)+1Fα(m)−1 = (−1)α(m)+1. F2
(3.2)
−F2
α(m)+1 ≡ (−1)α(m)+1 (mod m).
Vì Fα(m) ≡ 0 (mod m) và Fα(m)+1 ≡ Fα(m)−1 (mod m), nên
(s(m))2 ≡ (−1)α(m) (mod m).
Do đó
(3.3)
27
Ta suy ra (s(m))4 ≡ (−1)2α(m) = 1 (mod m). Do vậy β(m) | 4 và β(m) = 1, 2 hoặc 4. Định lý 3.8. Với p là một số nguyên tố lẻ bất kỳ, ta có β(pe) = β(p).
Chứng minh. Ta sẽ sử dụng lại ma trận Fibonacci U. Ta có
(mod pe+1).
Uα(pe+1) ≡ s(pe+1)I
(mod pe).
Ta có
Uα(pe) ≡ s(pe)I Do vậy Uα(pe) = s(pe)I + peB, với B ∈ M2(Z)nào đó. Suy ra
(mod pe+1).
U pα(pe) ≡ (s(pe)I + peB))p ≡ (s(pe))p I
Do đó α(pe+1) | pα(pe). Mặt khác α(pe) | α(pe+1). Do vậy α(pe+1) = α(pe) hoặc pα(pe). Từ đó ta suy ra = pi là một lũy thừa của p. Ta α(pe) α(p)
= pj, với j là một số tự nhiên nào đó. Rõ ràng, ta có
·
=
·
(=
).
đã biết rằng k(pe) k(p)
k(pe) k(p) α(pe) α(p) k(pe) α(pe) k(p) α(p) k(pe) α(p)
= β(pe) và
= β(p), nên
Vì k(pe) α(pe) k(p) α(p)
=
pi (1, 2, hoặc 4) = (1, 2, hoặc 4)pj.
Bởi vì ta đã giả sử p là một số lẻ, ta phải có pi = pj. Nghĩa là α(pe) α(p)
α(p) = k(pe)
α(pe), và ta có β(p) = β(pe).
k(p) ở trong
α(p) = k(pe)
. Điều này suy ra k(p) k(pe) k(p)
Hệ quả 3.9. Nếu p là một số nguyên tố lẻ và t là số nguyên lớn nhất sao cho α(pt) = α(p) thì α(pe) = pe−tα(p). Thực tế, số t này cũng là số nguyên lớn nhất sao cho k(pt) = k(p). Chứng minh. Điều này được suy ra từ đẳng thức α(pe) chứng minh của định lý trước.
28
Bây giờ ta sẽ nghiên cứu sâu hơn về hàm β(m). Định lý tiếp theo
trình bày những mối quan hệ hữu ích giữa β(m), α(m) và k(m).
Định lý 3.10. Cho m ≥ 3.
(i) Ta có β(m) = 4 nếu và chỉ nếu α(m) là lẻ.
(ii) Ta có β(m) = 1 nếu và chỉ nếu 4(cid:54) | k(m).
(iii) Ta có β(m) = 2 nếu và chỉ nếu 4 | k(m) và α(m) là chẵn.
≡ Fk(m)
Chứng minh. (i) Giả sử β(m) = 4. Vì s(m) có cấp bằng β(m) = 4 modulo p, nên (s(m))2 có cấp bằng 2 modulo p. Ta suy ra (s(m))2 (cid:54)≡ 1 (mod p). Măt khác, ta có (s(m))2 ≡ (−1)α(m) (mod p). Do vậy α(m) phải là số lẻ. Giả sử α(m) là lẻ. Trong trường hợp này, ta có (s(m))2 ≡ (−1)α(m) = −1 (mod p). Do đó cấp của s(m) modulo p chỉ có thể là 4, tức là β(m) = 4.
2 + 1 trong đồng nhất thức (mod m). Bởi 2 −1
2 +1
(ii) Giả sử 4 | k(m). Khi đó nếu đặt j = k(m) ở trên và chú ý rằng j là lẻ, ta nhận được Fk(m)
= Fk(m)
− Fk(m)
≡ 0 (mod m).
quan hệ truy hồi Fibonacci, ta suy ra
2 +1
2 −1
Fk(m) 2
Do đó α(m) | . Nói riêng β(m) (cid:54)= 1. k(m) 2
Bây giờ ta giả sử β(m) (cid:54)= 1. Khi đó β(m) = 2 hoặc 4. Ta biết rằng k(m) = α(m)β(m), do đó nếu β(m) = 4 thì ro ràng 4 | k(m). Nếu β(m) = 2 thì theo Định lý 3.10, α(m) là chẵn và ta vẫn có 4 | k(m).
(iii) Giả sử β(m) = 2. Khi đó theo (i), α(m) chẵn và theo (ii), 4 | k(m). Giả sử e | k(m) và α(m) là chẵn. Khi đó theo (i), β(m) (cid:54)= 4 và theo
(ii), β(m) (cid:54)= 1. Do vậy β(m) = 2.
Hệ quả 3.11. Nếu 4 | α(m) hoặc 8 | k(m) thì β(m) = 2.
Chứng minh. (a) Giả sử 4 | α(m). Khi đó α(m) chẵn và 4 | α(m) | k(m) = α(m)β(m). Do vậy β(m) = 2.
(b) Giả sử 8 | k(m). Khi đó hiển nhiên ta có 4 | k(m). Lại có k(m) = α(m)β(m) chia hết cho 8 và β(m) = 1, 2 hoặc 4. Ta suy ra α chẵn. Do vậy β(m) = 2.
29
Hệ quả 3.12. Ta có β(2) = β(4) = 1 và với e ≥ 3, thì β(2e) = 2.
Chứng minh. Kiểm tra trực tiếp ta thấy β(2) = β(4) = 1 và β(8) = 2. Theo Định lý 2.6, ta có k(2e) = 3 · 2e−1. Do đó 8 | k(2e) với mọi e ≥ 4. Áp dụng hệ quả trước, ta có β(2e) = 2.
Định lý 3.13. Cho p là một số nguyên tố lẻ. Nếu β(pe) = 2 thì 4 | α(pe).
Chứng minh. Trước hết ta sẽ chứng minh định lý cho trường hợp i e = 1. Giả sử β(p) = 2. Từ Định lý 3.10, ta có α(p) là chẵn. Từ đồng nhất thức
2 α(p) ≡ Fα(p)+1F−1 F1
2 α(p) (mod p).
(3.6), với n = 1 và r = − α(p), ta nhận được 1 2
1
2 α(p)+1F1
Chú ý rằng Fα(p)+1 = s(p) và s(p)2 ≡ (−1)α(p) (mod p). Nhân hai vế của đồng dư thức trên với Fα(p)+1 và áp dụng đồng nhất thức 1.2, ta thu được
2 α(p) (mod p).
Fα(p)+1F1
2 α(p) ≡ (−1)α(p)(−1) 2 α(p) không chia hết cho p, nên ta có
1
2 α(p)+1 (mod p).
Vì α(p) chẵn và F1
2 α(p)+1 = −1.
Fα(p)+1 ≡ (−1)
Vì β(p) = 2, nên ta có Fα(p)+1 (cid:54)≡ 1 (mod p). Do đó (−1) 1 Điều này suy ra 4 | α(p).
Bây giờ ta xét trường hợp e ≥ 2. Vì p lẻ nên β(pe) = β(p) và do vậy β(p) = 2. Theo phần trên, ta suy ra 4 | α(p). Vì α(p) | α(pe) nên 4 | α(pe).
Định lý tiếp theo cho ta một phương pháp tìm β([m, n]) nếu ta biết
β(m) và β(n).
Định lý 3.14. Cho trước β(m) và β(n). Giả sử β(m) ≥ β(n). Giá trị của β([m, n]) được xác định như sau.
1
β([m, n]) = nếu β(m) = β(n) = 1 nếu (n = 2,β(m) = 4); hoặc (nếu β(m) = β(n) = 4) 4
2 các trường hợp còn lại
30
Chứng minh. Ta viết
α(m) = 2ra, β(m) = 2s, k(m) = 2ta, α(n) = 2wb, β(n) = 2x, k(n) = 2yb,
trong đó a và b là các số nguyên lẻ. Khi đó
k([m, n]) = [k(m), k(n)] = 2max(t,y) · [a, b], α([m, n]) = [α(m), α(n)] = 2max(r,w) · [a, b].
Do vậy
= 2max(t,y)−max(r,w).
β([m, n]) = k([m, n]) α([m, n])
Chú ý rằng r + s = t và w + x = y.
Chú ý rằng các kết quả trong Định lý 3.10 có thể phát biểu lại sử
• Nếu s = 0 thì t = 0 và r = 0 (cho m = 2); hoặc t = 1 và r = 1 (với
dụng r, s, và t như sau:
• Nếu s = 1 thì t ≥ 2 và r ≥ 1.
• Nếu s = 2 thì r = 0 và do đó, t = 2.
m > 2).
Ta có phát biểu tương tự cho w, x, và y.
Ta xét các sau.
Trường hợp 1: β(m) = β(n). Khi đó s = x. Ta có
max(t, y) − max(r, w) = max(r + s, w + x) − max(r, w) = s = x.
Do đó β([m, n]) = 2s = 2x = β(m) = β(n). Trường hợp 2: β(m) = 4; β(n) = 1. Khi đó s = 2 và x = 0. Vì s = 2 nên ta có r = 0 và t = 2. Vì x = 0 ta có, hoặc là w = 0 (với n = 2), hoặc là w = 1 (với n > 2 ). Trường hợp con (2a): n = 2. Khi đó
max(t, y) − max(r, w) = 2 − 0 = 2.
Do đó β([m, n]) = 22 = 4.
31
Trường hợp con (2b): n > 2. Khi đó w = 1 và vì thế y = 1. Ta có
max(t, y) − max(r, w) = 2 − 1 = 1.
Do đó β([m, n]) = 21 = 2. Trường hợp 3: β(m) = 2 và β(n) = 1. Khi đó s = 1 và x = 0. Do s = 1 ta có t ≥ 2 và r ≥ 1. Do x = 0 nên hoặc là w = 0 (với n = 2), hoặc là w = 1 (với n > 2). Trường hợp con (3a): n = 2. Khi đó vì x = 0, w = 0, nên y = 0. Ta có
max(t, y) − max(r, w) = t − r = s = 1.
Do đó β([m, n]) = 21 = 2. Trường hợp con (3b): n > 2. Khi đó vì x = 0, w = 1, nên y = 1. Ta có
max(t, y) − max(r, w) = t − r = s = 1.
Vì thế β([m, n]) = 21 = 2. Trường hợp 4: β(m) = 4 và β(n) = 2. Khi đó s = 2 và x = 1. Ta suy ra r = 0, t = 2, và w ≥ 1, y ≥ 2. Khi đó
max(t, y) − max(r, w) = y − w = x = 1.
Vì vậy β([m, n]) = 21 = 2. Phép chứng minh được hoàn thành.
Ta thu được hai hệ quả thú vị như sau.
Hệ quả 3.15. Nếu 3 | m thì β(m) = 2.
Chứng minh. Vì β(3) = 2 nên β(3e) = β(3) = 2. Viết m dưới dạng m = 3en trong đó 3 (cid:45) n. Khi đó theo Định lý 3.14, ta có β(m) = β([3e, n]) = 2.
Hệ quả 3.16. Ta có β(m) = 1 nếu và chỉ nếu 8 (cid:45) m và α(p) ≡ 2 (mod 4) với mọi số nguyên tố lẻ p là ước của m.
Chứng minh. Giả sử m có phân tích ra thừa số nguyên tố m = ∏ pei i , ở đây pi là số nguyên tố, ei là số nguyên dương và ta có thể giả sử p1 < p2 < · · · .
32
i ) = 1 với mọi i. Nếu p1 = 2 thì theo Hệ quả 3.12 ta có e1 ≤ 2 và do đó 8 (cid:45) m. Và với mọi ước lẻ pi của m ta có 1 = β(pei i ) = β(pi). Định lý 3.10 (i) nói rằng nếu α(pi) ≡ 1 hoặc 3 (mod 4) thì β(pi) = 4. Định lý 3.10 (iii) nói rằng nếu α(pi) ≡ 0 (mod 4) thì β(pi) = 2. Do đó, để β(pi) = 1 thì ta phải có α(pi) ≡ 2 (mod 4).
Giả sử β(m) = 1. Từ Định lý 3.14, ta suy ra β(pei
Bây giờ ta giả sử rằng 8 (cid:45) m và α(pi) ≡ 2 (mod 4) với mọi ước nguyên tố lẻ pi của m. Nếu p1 = 2 thì e1 ≤ 2 và β(pe1 1 ) = 1. Xét pi là một ước nguyên tố lẻ bất kỳ. Vì α(pi) ≡ 2 (mod 4) nên β(pi) = 1 theo Định lý 3.10 và Định lý 3.13. Vì pi lẻ nên β(pei i ) = β(pi) = 1. Từ Định lý 3.14, ta suy ra β(m) = 1.
Ta biết rằng với hợp số m thì β(m) có thể được tính bằng cách phân tích m ra thừa số nguyên tố. Ta cũng biết rằng với một số nguyên tố p lẻ thì β(pe) = β(p). Một câu hỏi nảy sinh là liệu có thể tính được β(p) cho số nguyên tố p lẻ? Kết quả sau đây có thể được tìm thấy trong [5] và cho một số thông tin về β(p).
Định lý 3.17. Cho p là một số nguyên tố lẻ.
(a) Nếu p ≡ 11 hoặc 19 (mod 20) thì β(pe) = 1.
(b) Nếu p ≡ 3 hoặc 7 (mod 20) thì β(pe) = 2.
(c) Nếu p ≡ 13 hoặc 17 (mod 20) thì β(pe) = 4.
(d) Nếu p ≡ 21 hoặc 29 (mod 40) thì β(pe)6 = 2.
Chứng minh. Ta chỉ cần chứng minh cho trường hợp e = 1. Vì β(p) là bậc của s(p) modulo p và (s(p))p−1 ≡ 1 (mod p) theo Định lý Fermat nhỏ, ta có β(p) | p − 1. Như vậy nếu p ≡ 3 (mod 4)) thì β(p) (cid:54)= 4.
Giả sử p = 5t ± 2. Khi đó Fp ≡ −1 (mod p) và Fp+1 ≡ 0 (mod p). Ta suy α(p) | p + 1 nhưng k(p) (cid:45) p + 1. Do đó α(p) (cid:54)= k(p) và β(p) (cid:54)= 1.
(a) Vì p ≡ 11 hoặc 19 (mod 20), nên p ≡ 3 (mod 4). Do đó β(p) (cid:54)= 4. Giả sử β(p) = 2. Khi đó theo Định lý 3.10, 4 | k(p). Do p = 5t ± 1 ta có k(p) | p − 1, và vì vậy 4 | p − 1. Tuy nhiên, đây là mâu thuẫn do p − 1 ≡ 10 hoặc 18 (mod 20). Như vậy β(p) = 1.
b Vì p ≡ 3 (mod 4), nên β(p) (cid:54)= 4. Bây giờ p = 5t ± 2 và do đó
β(p) (cid:54)= 1. Tóm lại β(p) = 2.
33
(c) Như trong phần trước, p = 5t ± 2 và vì thế β(p) (cid:54)= 1. Vì p = 5t ± 2, nên k(p) | 2p + 2. Suy ra α(p) | p + 1. Trong trường hợp này p ≡ 1 (mod 4) vì vậy 4 (cid:45) p + 1. Do đó 4 (cid:45) α(p). Áp dụng Định lý 3.13 ta có β(p) (cid:54)= 2. Do đó β(p) = 4.
(d) Giả sử β(p) = 2. Theo Định lý 3.13, 4 | α(p) và do đó 8 | k(p). Ngoài ra, vì p = 5t ± 1, nên Định lý 2.10 ta có k(p) | p − 1. Như vậy 8 | p − 1. Tuy nhiên, p − 1 ≡ 20 hoặc 28 (mod 40) vì thế rõ ràng là 8 (cid:45) p − 1. Ta nhận được một điều mâu thuẫn. Như vậy β(p) (cid:54)= 2.
Phép chứng minh được hoàn thành.
Chúng ta muốn biết liệu có thể nói được gì về các số nguyên tố không thỏa mãn điều kiện trong định lý trên, cụ thể là với những số nguyên tố p mà p ≡ 1 hoặc 9 (mod 40). Ta có thể nói gì cụ thể hơn cho trường hợp số nguyên tố p mà p ≡ 21 hoặc 29 (mod 40)? J. Vinson [5] đưa các ví dụ sau đây để chứng tỏ rằng kết quả của ông ta là "đầy đủ":
β(521) = 1, β(41) = 2, β(761) = 4, β(809) = 1, β(409) = 2, β(89) = 4,
Với p ≡ 1 (mod 40) : Với p ≡ 9 (mod 40) : Với p ≡ 21 (mod 40) : β(101) = 1, β(61) = 4, β(109) = 4. Với p ≡ 29 (mod 40) : β(29) = 1,
34
Kết luận
Luận văn đã trình bày những vấn đề chính sau đây.
- Một số tính chất và đồng nhất thức liên quan đến dãy Fibonacci.
- Một số kết quả về chu kỳ của dãy Fibonacci modulo m.
- Một số kết quả về vị trí số 0 đầu tiên, cũng như số số 0 trong một
chu kỳ của dãy Fibonacci modulo m.
35
Tài liệu tham khảo
[1] Burton D. M (1994), Elementary Number Theory, Third Edition, Wm.
C. Brown Publishers, Dubuque, Iowa.
[2] Robinson D.W. (1963), "The Fibonacci matrix modulo m," Fibonacci
Quarterly 1, pp. 29-36.
[3] Renault M. (1996), "The Fibonacci sequence under various moduli",
Master thesis, Wake Forest University.
[4] Vajda S. (1989), Fibonacci & Lucas Numbers, and the Golden Section,
Ellis Horwood Limited, Chichester, England.
[5] Vinson J. (1963), "The relation of the period modulo m to the rank of apparition of m in the Fibonacci Sequence", Fibonacci Quarterly, 1, pp. 37-45.
[6] Wall D. D (1960), "Fibonacci Series Modulo m", American Mathemat-
ical Monthly, 67, pp. 525-532.
