Luận văn Thạc sĩ Toán học: Dãy fibonacci modulo m

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:38

Thêm vào BST

Báo xấu

28
lượt xem 4
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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. Đê hiểu rõ hơn, mời các bạn tham khảo chi tiết nội dung luận văn này.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Toán học: Dãy fibonacci modulo m

ĐẠ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ị 3 1.1. Dãy Fibonacci . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2. Công thức Binet . . . . . . . . . . . . . . . . . . . . . . . . 7 1.3. Luật thuận nghịch bậc hai . . . . . . . . . . . . . . . . . . 8 2 Dãy Fibonacci mod m 11 2.1. Một số tính chất cơ bản . . . . . . . . . . . . . . . . . . . . 11 2.2. Chu kỳ của dãy Fibonacci modulo pe . . . . . . . . . . . . 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. Dãy Fibonacci là dãy cho bởi F0 = 0, F1 = 1 và Fn+2 = Fn+1 + Fn , ∀n ≥ 0. Dưới đây là một số số hạng đầu tiên của dãy Fibonacci. Fn : 0 1 1 2 3 5 8 13 21 34 55 . . . Đồng nhất thức 1.1. Fm+n = Fm−1 Fn + Fm Fn+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−1 F1 + Fm F2 . 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−1 Fk + Fm Fk+1 và Fm+(k−1) = Fm−1 Fk−1 + Fm Fk .
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−1 Fk+1 + Fm Fk+2 , và do vậy đồng nhất thức đúng với n = k + 1. Ví dụ, ta có F12 = F8+4 = F7 F4 + F8 F5 = 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, . . .. n : ··· −7 − 6 −5 − 4 −3 − 2 −1 0 12 34 ··· Fn : · · · 13 − 8 5 −3 2 −1 10 11 23 ··· 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+1 Fn . 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 ( Fm Fn+1 − Fm+1 Fn ). Đị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−1 Fm + Fmk Fm+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. Đồng nhất thức 1.5. Ta có Fn2 + Fn2+1 = F2n+1 . Chứng minh. Từ đồng nhất thức 1.1, ta có F2n+1 = Fn+(n+1) = Fn−1 Fn+1 + Fn Fn+2 = Fn−1 Fn+1 + Fn ( Fn + Fn+1 ) = Fn2 + ( Fn−1 + Fn ) Fn+1 = Fn2 + Fn2+1 . 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+1 Fn−1 − F2n = (−1)n . Chứng minh. Ta có Fn+1 Fn−1 − F2n = ( Fn−1 + Fn ) Fn−1 − F2n = Fn2−1 + Fn ( Fn−1 − Fn ) = Fn2−1 − Fn Fn−2 = −( Fn Fn−2 − Fn2−1 ). 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 −( Fn Fn−2 − F2n−1 ) = (−1)2 ( Fn−1 Fn−3 − F2n−2 ) = (−1)3 ( Fn−2 Fn−4 − F2n−3 ) .. . = (−1)n ( F1 F− 1 − F02 ) = (−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−1 Gm + Fn Gm+1 . Chứng minh. Với trường hợp n = 0 và n = 1 ta có Gm = F−1 Gm + F0 Gm+1 Gm+1 = F0 Gm + F1 Gm + 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 ( Fn Gm+1 − Fn+1 Gm ). 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 √ √ Đặt α = (1 + 5)/2 và β = (1 − 5)/2. Khi đó ta có Công thức Binet tính số Fn theo n. Mệnh đề 1.9. Với mọi n ≥ 0, ta có αn − βn Fn = , α−β 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 đúng đến n ≥ 1. Ta có (α − β) Fn+1 = (α − β) Fn + (α − β) Fn−1 = α n − β n + α n −1 − β n −1 = α n + α n −1 − ( β n + β 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 (α − β) Fn+1 = αn+1 − βn+1 , công thức đúng với n + 1. Đồng nhất thức 1.10. Ta có n n n 2 2n−1 Fn = + 5+ 5 +··· 1 3 5 Chứng minh. Ta có αn − βn Fn = α−β 1 √ √ = √ (1 + 5) n − (1 − 5) n 2n 5 " # n √ n √ 1 n k n k = √ ∑ 5 − ∑ (−1)k 5 2n 5 k =0 k =0 k k 1 n √ n √ 3 n √ 5 = √ 2 5+2 5 +2 5 +··· 2n 5 1 3 5 1 n n n 2 = ( + 5 + 5 + · · · ). 2n −1 1 3 5 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 - 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. Đị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 dư toàn phương) modulo p nếu và chỉ nếu a 2 ≡ 1( mod p) (tương ứng, p −1 a 2 ≡ −1( mod 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. a 1 nếu a là thặng dư toàn phương modulo p Ta định nghĩa: = p −1 nếu a không là thặng dư toàn phương modulo p Ký hiệu này được gọi là ký hiệu Legendre. 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. a2 1. = 1. p ab a b 2. = . p p p a p −1 3. ≡ a 2 ( mod p) (Tiêu chuẩn Euler). p a b 4. Nếu a ≡ b ( mod p) thì = . p p −1 5. bằng 1 hoặc −1 tùy theo p ≡ 1 ( mod4) hay p ≡ 3 ( mod4). p 2 2 6. Khi đó = 1 và nếu p ≡ 1 ( mod8) hoặc p ≡ 7 ( mod8); và = p p 1 nếu p ≡ 3 ( mod8) hoặc p ≡ 5 ( mod8). Đị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 ) hoặc q≡ 1 (mod 4) thì 4 p q p q = ; và nếu p ≡ q ≡ 3 ( mod4) thì =− . q p 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. 5 p Chứng minh. Theo Luật thuận nghịch bậc hai ta có = do 5 là p 5 một số nguyên tố có dạng 4t + 1. Ta có 5 5t + 1 1 = = = 1, 5t + 1 5 5 5t − 1 5 4 = = = 1. 5t − 1 5 5 Ta cũng có 5 5t + 2 2 = = = −1, 5t + 2 5 5 5t − 2 5 3 )= = = −1. 5t − 2 5 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 cho ( Gs mod m, Gs+1 mod m) = ( Gt mod m, Gt+1 mod m). 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. Do vậy ( Gs−1 mod m, Gs mod m) = ( Gt−1 mod m, Gt mod m). Tiếp tục quá trình này ta suy ra ( G0 mod m, G1 mod m) = ( Gt−s mod m, Gt−s+1 mod m). Đặ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 Fk+1 Fk−1 − Fk2 = (−1)k , 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 e e (ii) Nếu m có phân tích ra thừa số nguyên tố m = ∏ pi i thì h(m) = lcm[h( pi i )], e bội chung nhỏ nhất của h( pi i ). (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. e e (ii) Đặt h := lcm[h( pi i )] Theo (i), ta có h( pi i ) | h(m) với mọi i. Do vậy h | h ( m ). e e Vì h( pi i ) | h nên G (mod pi i ) lặp lại theo các khối có độ dài h. Do đó e e Gh ≡ G0 và Gh+1 ≡ G1 (mod pi i ) với mọi i. Vì các pi i là nguyên tố cùng 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). (iii) Do m | [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 e tố [m, n] = p11 . . . pet t . Khi đó e e h([m, n]) = h( p11 . . . pet t ) = [ h( p11 . . . h( pet t )]. e e Vì pi i chia hết m hoặc n với mọi i, nên h( pi i ) chia hết h(m) hoặc h(n) với e mọi i. Do đó [h( pi i ) . . . h( pet t )] | [h(m), h(n)]. Nói cách khác, h([m, n]) | [h(m), h(n)]. Do đó h([m, n]) = [h(m), h(n)]. 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ó F3·2r−2 ≡ 0 (mod 2r ) và F3·2r−2 +1 ≡ 2r−1 + 1 (mod 2r ). 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 - 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 ). Ta có (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 ). Do vậy ( 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 F3·2r−2 ≡ 0 hoặc 2r (mod 2r+1 ), Ta có (2r )2 = 22r ≡ 0 (mod 2r+1 ). Do đó ( F3·2r−2 )2 ≡ 0 (mod 2r+1 ). 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 6= 1 (mod 2)e+1 . Ta suy ra k(2e+1 ) 6= 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 0 1 U= . 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 1 0 I= , ma trận đơn vị cỡ 2 × 2. 0 1 Bổ đề 2.7. Các khẳng định sau là đúng. n Fn−1 Fn (i) Với mọi n ≥ 1, ta có U = . Fn Fn+1 (ii) Với m ≥ 2, ta có U k(m) = I + mB ≡ I (mod m), với B ∈ M2 (Z) nào đó. (iii) Nếu U n ≡ 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ó F F 0 1 U n +1 = U n · U = n −1 n · Fn Fn+1 1 1 Fn Fn−1 + Fn Fn Fn+1 = = . Fn+1 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 " # Fk(m)−1 Fk(m) F−1 F0 U k(m) = ≡ =I (mod m). Fk(m) Fk(m)+1 F0 F1
16 Do vậy U k(m) = I + mB với B ∈ M2 (Z). (iii) Giả sử U n ≡ I (mod m). Khi đó, từ phần 1 ta suy ra Fn ≡ 0 (mod m) và Fn+1 ≡ 1 (mod m). 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−t k( 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. e Bây giờ ta xét trường hợp p > 2. Ta có U k( p ) = I + pe B, với B ∈ M2 (Z) nào đó. Suy ra U pk( pe) = ( I + pe B) p p p p −1 e p p −2 e 2 =I + I ( p B) + I ( p B) + · · · 1 2 e Vì p | ( pi), với mọi i = 1, . . . , p − 1 (chú ý rằng p lẻ). Do vậy U pk( 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 ). 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ó U k( pe) = I + pe B với p - B. Do đó e U pk( p ) = ( I + pe B) p p p p −1 e p p −2 e 2 =I + I ( p B) + I ( p B) + · · · 1 2 ≡ I + pe+1 B (mod pe+2 ). Do đó e +1 ) e U k( p = U pk( p ) ≡ I + pe+1 B 6≡ I (mod pe+2 ). Điều này kéo theo k( pe+1 ) 6= 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 đó (1) (np) ≡ 0 (mod p) với 1 ≤ n ≤ p − 1. (2) ( p− 1 n n ) ≡ (−1) (mod p ) với 0 ≤ n ≤ p − 1. (3) ( p+ 1 n ) ≡ 0 (mod p ) với 2 ≤ n ≤ p − 1. p! Chứng minh. (1) Xét 1 ≤ n ≤ p − 1. Đăt a := (np) = . Khi đó 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) (mod p). Do vậy p−1 b−1 p = − ≡ −(−1) = (−1)2 (mod p). 2 2 1 Chứng minh bằng quy nạp ta có ( p− 1 n n ) ≡ (−1) (mod p ). (3) Với 2 ≤ n ≤ p − 1, ta có p+1 p p = + ≡0 (mod p). n 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ó p p p p −1 2 p−1 Fp = + 5+···+ 5 2 . 1 3 p