Luận văn Thạc sĩ Toán học: Dãy hồi quy bậc hai

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

Thêm vào BST

Báo xấu

25
lượt xem 3
download

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

Mục đích chính của luận văn này là trình bày về Định lý Carmichael về sự tồn tại ước nguyên thủy trong dãy Lucas thực. Cụ thể, luận văn được chia làm ba chương: Các kiến thức chuẩn bị về đa thức chia đường tròn và số nguyên đại số; dãy hồi quy bậc hai; Phát biểu và chứng minh Định lý Carmichael về sự tồn tại ước nguyên thủy trong dãy Lucas thực, định lý Zsigmondy liên quan.

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 hồi quy bậc hai

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC NGUYỄN NGỌC ÁNH DÃY HỒI QUY BẬC HAI LUẬN VĂN THẠC SĨ TOÁN HỌC Thái Nguyên - 2016
ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC NGUYỄN NGỌC ÁNH DÃY HỒI QUY BẬC HAI LUẬN VĂN THẠC SĨ TOÁN HỌC Chuyên ngành: Phương pháp Toán sơ cấp Mã số: 60 46 01 13 NGƯỜI HƯỚNG DẪN KHOA HỌC TS. NGUYỄN DUY TÂN Thái Nguyên - 2016
i Mục lục Lời mở đầu 1 1 Kiến thức chuẩn bị 3 1.1 Đa thức chia đường tròn . . . . . . . . . . . . . . . . . . . 3 1.1.1 Căn đơn vị . . . . . . . . . . . . . . . . . . . . . 3 1.1.2 Đa thức chia đường tròn . . . . . . . . . . . . . . 5 1.2 Sơ lược về số nguyên đại số . . . . . . . . . . . . . . . . . 8 2 Dãy hồi quy bậc hai 10 2.1 Định nghĩa . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.2 Một số ví dụ về dãy hồi quy bậc hai . . . . . . . . . . . . 12 2.2.1 Dãy Fibonacci . . . . . . . . . . . . . . . . . . . 12 2.2.2 Dãy Mersenne . . . . . . . . . . . . . . . . . . . 12 2.3 Dãy Lucas . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.3.1 Định nghĩa và ví dụ . . . . . . . . . . . . . . . . . 13 2.3.2 Ước nguyên tố của số hạng trong dãy Lucas . . . . 13 3 Định lý ước nguyên thủy 20 3.1 Định lý Carmichael . . . . . . . . . . . . . . . . . . . . . 20 3.1.1 Một điều kiện đủ về tồn tại ước nguyên thủy . . . . 21 3.1.2 Chứng minh Định lý Carmichael . . . . . . . . . . 25 3.2 Định lý Zsigmondy . . . . . . . . . . . . . . . . . . . . . 29 3.3 Một số bài tập ứng dụng . . . . . . . . . . . . . . . . . . 32 Kết luận 37 Tài liệu tham khảo 38
1 Lời mở đầu Dãy Lucas thực là dãy được định nghĩa theo công thức truy hồi như sau u0 = 0, u1 = 1, . . . , un+2 = a1 un+1 + a2 un , ở đây a1 a2 6= 0; a1 và a2 là các số nguyên nguyên tố cùng nhau thỏa mãn α n − α2n a21 −4a2 > 0. Một cách tương đương, ta có thể định nghĩa un = 1 , ∀n ≥ α1 − α2 0, với α1 , α2 là nghiệm thực phân biệt của đa thức đặc trưng f (X) = X 2 − a1 X − a2 . Một ví dụ quan trọng về dãy Lucas thực là dãy Fibonacci (Fn )n≥0 : F0 = 0, F1 = 1, Fn+2 = Fn+1 + Fn , ∀n ≥ 0. Cho (un ) là một dãy Lucas thực như trên. Dễ thấy un là nguyên với mọi n. Một câu hỏi cơ bản là chúng ta có thể nói gì về các ước nguyên tố của các số hạng un . Định nghĩa. Một số nguyên tố p được gọi là ước nguyên thủy của số hạng un nếu p chia hết un nhưng p không chia hết um với mọi 0 < m < n. Một định lý quan trọng của Carmichael [1] nói rằng, trừ một vài trường hợp riêng, mọi số hạng trong dãy Lucas đều có ước nguyên thủy. Định lý Carmichael. Cho (un )n≥0 là một dãy Lucas thực và n 6= 1, 2, 6. Khi đó un có một ước nguyên thủy trừ trường hợp un = F12 , số hạng thứ 12 trong dãy Fibonacci. Mục đích chính của luận văn này là trình bày về Định lý Carmichael về sự tồn tại ước nguyên thủy trong dãy Lucas thực. Cụ thể, luận văn được chia làm ba chương. Chương 1 trình bày các kiến thức chuẩn bị về đa thức chia đường tròn và số nguyên đại số. Chương 2
2 trình bày về dãy hồi quy bậc hai, ví dụ về dãy hồi quy bậc hai và dãy Lucas. Trong chương này cũng trình bày về ước số nguyên tố của số hạng trong dãy Lucas. Chương 3 trình bày phát biểu và chứng minh Định lý Carmichael về sự tồn tại ước nguyên thủy trong dãy Lucas thực, Định lý Zsigmondy liên quan. Ở cuối chương này chúng tôi cũng đưa ra một số bài tập ứng dụng trong toán sơ cấp. Sau một thời gian nỗ lực nghiên cứu tôi đã hoàn thành luận văn tốt nghiệp của mình. Trong suốt quá trình học tập và nghiên cứu, tôi đã nhận được sự quan tâm, khích lệ của tất cả các thầy cô, bạn bè, đồng nghiệp và gia đình. Trước tiên, tôi xin gửi lời cảm ơn chân thành và sâu sắc nhất đến thầy tôi- TS. Nguyễn Duy Tân. Thầy đã hết sức tận tình dìu dắt tôi từ những bước đi đầu tiên khi bắt đầu thực hiện luận văn. Tôi cũng xin gửi lời cảm ơn chân thành tới các thầy cô ở trường Đại học Khoa học-Đại học Thái Nguyên đã luôn tận tình giúp đỡ, theo sát tôi trong suốt quá trình học tập và thực hiện luận văn này. Tôi xin gửi lời cảm ơn tới các đồng nghiệp trong tổ Toán-Tin trường THPT Lý Thường Kiệt-tỉnh Yên Bái luôn tạo điều kiện tốt nhất giúp tôi hoàn thành khóa học. Cuối cùng, tôi xin gửi lời cảm ơn tới các bạn bè, gia đình đã luôn ở bên hỗ trợ, cổ vũ và động viên tôi trong suốt quá trình học tập và nghiên cứu. Tác giả Nguyễn Ngọc Ánh
3 Chương 1 Kiến thức chuẩn bị Trong chương này chúng tôi trình bày một số kiến thức chuẩn bị về đa thức chia đường tròn, công thức nghịch đảo M¨obius và sơ lược về số nguyên đại số. Tài liệu thàm khảo chính được sử dụng là [2]. 1.1 Đa thức chia đường tròn 1.1.1 Căn đơn vị Định nghĩa 1.1.1. Cho n là một số nguyên dương. Một số phức ζ được gọi là căn bậc n của đơn vị nếu ζ n = 1. Ta biết rằng có n căn bậc n của đơn vị, 2πi 2 2πi n là những số e2πi/n , e n , ..., e n . Định nghĩa 1.1.2. Cho n là số nguyên dương và ζ là một căn bậc n của đơn vị. Khi đó số nguyên dương nhỏ nhất k thỏa mãn ζ k = 1 được gọi là bậc của ζ và được kí hiệu là ord(ζ ). Bổ đề 1.1.3. Cho n là số nguyên dương và ζ là một căn bậc n của đơn vị. Khi đó với mọi số nguyên k, ζ k = 1 nếu và chỉ nếu ord(ζ )|k. Nói riêng, ord(ζ )|n. Chứng minh. Gọi d = ord(ζ ). Nếu d | k, thì rõ ràng ζ k =1. Mặt khác giả sử rằng ζ k =1. Khi đó tồn tại hai số nguyên q, r với 0 ≤ r ≤ d − 1 sao cho k = dq + r. Ta có 1 = ζ k = ζ qd+r = ζ r . Nhưng 0 ≤ r < d và d là số nguyên dương nhỏ nhất thỏa mãn ζ d = 1, do vậy r = 0.
4 Hệ quả 1.1.4. Cho ζ là một căn của đơn vị. Khi đó với hai số nguyên k và l bất kỳ, ζ k = ζ l nếu và chỉ nếu k ≡ l mod ord(ζ ). Nói riêng, nếu 1 ≤ k, l ≤ ord(ζ ), thì ζ k = ζ l nếu và chỉ nếu k = l. Chứng minh. Chú ý rằng ζ k = ζ l nếu và chỉ nếu ζ k−l = 1. Hệ quả được suy ra từ Bổ đề 1.1.3. Định nghĩa 1.1.5. Cho n là số nguyên dương và ζ là một căn bậc n của đơn vị. Khi đó ζ được gọi là căn nguyên thủy bậc n của đơn vị nếu ord(ζ ) = n. Bổ đề 1.1.6. Giả sử rằng ζ là căn nguyên thủy bậc n của đơn vị. Khi đó tập ζ , ζ 2 , . . . , ζ n là tập tất cả các căn bậc n của đơn vị. Chứng minh. Với mọi số nguyên k, ζ k là một căn bậc n của đơn vị vì ζ kn = 1. Theo định nghĩa về căn nguyên thủy bậc n của đơn vị, các số ζ 1 , . . . , ζ n là phân biệt. Nhưng vì chỉ tồn tại n căn bậc n của đơn vị, nên ta có điều phải chứng minh. Bổ đề 1.1.7. Cho n, k là các số nguyên dương và ζ là căn nguyên thủy bậc n của đơn vị. Khi đó ζ k là căn nguyên thủy bậc n của đơn vị nếu và chỉ nếu gcd(k, n) = 1. Chứng minh. Gọi d = ord(ζ k ). Ta có (ζ k )n = (ζ n )k = 1. Do đó d | n. Mặt khác ta có ζ kd = 1. Từ Bổ đề 1.1.3, suy ra n | kd. Nếu gcd(k, n) = 1, thì n | d. Kết hợp với d | n, ta suy ra d = n. Do đó ζ k là nguyên thủy. n k Nếu gcd(k, n) = r > 1 thì (ζ k ) r = (ζ n ) r = 1. Suy ra d | n/r. Do vậy d ≤ n/r < r và ζ k không nguyên thủy bậc n. Định nghĩa 1.1.8. Hàm Euler ϕ : N → N được định nghĩa như sau. Với mỗi n ≥ 1, ϕ(n) là số các số k, 1 ≤ k ≤ n, mà k nguyên tố cùng nhau với n. Chẳng hạn, ϕ(1) = 1, ϕ(2)=1, ϕ(3)=2, ϕ(4)=2. Ta có ngay hệ quả sau. Hệ quả 1.1.9. Cho n là số nguyên dương. Khi đó có đúng ϕ(n) căn nguyên thủy bậc n của đơn vị.
5 1.1.2 Đa thức chia đường tròn Định nghĩa 1.1.10. Cho n là số nguyên dương. Thì đa thức chia đường tròn thứ n, ký hiệu Φn , là đa thức (hệ số đầu bằng 1) mà các nghiệm của nó chính là các căn nguyên thủy bậc n, tức là Φn (X) ≡ ∏ (X − ζ ). n ζ =1 ord(ζ )=n Vì có đúng ϕ(n) căn nguyên thủy bậc n của đơn vị, nên bậc của Φn là ϕ(n). Định lý 1.1.11. Nếu n là một số nguyên dương, thì X n − 1 ≡ ∏ Φd (X). d|n Chứng minh. Các nghiệm của X n − 1 chính là các căn bậc n của đơn vị. Mặt khác, nếu ζ là một căn bậc n của đơn vị và d = ord(ζ ), thì ζ là một căn nguyên thủy bậc d của đơn vị và do đó là một nghiệm của Φd (X). Vì d | n, nên ζ là một nghiệm của vế phải. Do vậy ta thấy rằng hai đa thức bên vế trái và vế phải có cùng tập các nghiệm. Vì chúng là cùng monic (đa thức hệ số đầu bằng 1), nên chúng bằng nhau. Chú ý rằng, việc so sánh bậc của đa thức cho ta n = ∑ ϕ(n). d|n Ta cũng có công thức truy hồi tính Φn như sau Xn − 1 Φn (X) = . ∏ Φd (X) d|n d6=n Do vậy Φn (X) có hệ số hữu tỷ. Hơn nữa vì các đa thức Φd (X) đều là monic, nên ta có thể chứng minh được Φn (X) ∈ Z[X]. (Nếu dùng khái niệm số nguyên đại số ở mục sau, ta có thể chứng minh khẳng định này như sau. Rõ ràng ζ k đều là các số nguyên đại số, do vậy các hệ số của Φn (X) cũng là các số nguyên đại số. Mặt khác, chúng là các số hữu tỷ, do vậy chúng phải
6 là các số nguyên.) Dưới đây là một số giá trị của Φn (X) Φ1 (X) = X − 1, Φ2 (X) = X + 1, Φ3 (X) = X 2 + X + 1, Φ4 (X) = X 2 + 1, Φ5 (X) = X 4 + X 3 + X 2 + X + 1, Φ6 (X) = X 2 − X + 1. Dùng công thức nghịch đảo M¨obius ta có thể đưa ra công thức trực tiếp tính Φn . Ta nhắc lại hàm M¨obius và công thức nghịch đảo M¨obius ở dưới đây. Định nghĩa 1.1.12. Hàm M¨obius µ : Z+ → {−1, 0, 1} được định nghĩa như sau    1 nếu n = 1  µ(n) = (−1)k nếu n là tích của k số nguyên tố phân biệt    0 trong các trường hợp còn lại. Dễ thấy µ là nhân tính, tức là, µ(mn) = µ(m)µ(n) nếu m và n nguyên tố cùng nhau. Định lý 1.1.13. Nếu n là một số nguyên dương, thì ( 1 khi n = 1 ∑ µ(d) = 0 khi n ≥ 2. d|n Chứng minh. Điều này hiển nhiên đúng với n = 1. Giả sử n ≥ 2. Gọi T là tích của tất cả các số nguyên chia hết n, tức là T= ∏ p. p nguyên tố,p|n Với ước d của n mà không chia hết T thì d sẽ không là tích của các số nguyên tố phân biệt (nó sẽ chứa một nhân tử bình phương), và do vậy µ(d) = 0. Do
7 đó, ta có ∑ µ(d) = ∑ µ(d). d|n d|T Lấy p là số nguyên tố bất kỳ chia hết T . Thì ∑ = ∑T µ(d) + µ(pd) = ∑T µ(d) − µ(d) = 0. d|T d| p d| p Định lý 1.1.14 (Công thức nghịch đảo M¨obius). Giả sử rằng F và f : Z+ → R là các hàm sao cho F (n) = ∑ f (d) . d|n Khi đó n f (n) = ∑ µ (d) F( ). d|n d Chứng minh. Ta có n ∑ µ (d) F( d ) = ∑ µ (d) ∑n f (t) . d|n d|n t| d Mỗi ước t của n/d cũng là ước của n. Do vậy ta có ∑ µ (d) ∑n f (t) = ∑ f (t) ∑ µ(d) = ∑ f (t) ∑n µ(d). d|n t| d t|n d|n t|n d| t t| dn Từ Định lý 1.1.13 , ta có  1 nếu t = n ∑n µ(d) =  d|t 0 trong các trường hợp còn lại. Do vậy ∑ f (t) ∑n µ(d) = f (n) . t|n d| t Ta cũng có phiên bản nhân tính của Định lý 1.1.14 như ở dưới đây.
8 Định lý 1.1.15. Giả sử rằng F, f : Z+ → R là các hàm cho bởi F (n) = ∏ f (d) . d|n Thì n µ(d) f (n) = ∏ F . d|n d Chứng minh. Chứng minh của định lý này được thực hiện giống như chứng minh của Định lý 1.1.14, ngoại trừ mỗi tổng được thay thế bằng các tích và mỗi đa thức với µ-hàm được thay thế bởi lũy thừa của nó  µ(d) n µ(d) ∑ µ(d) d|n,t| dn ∏F = ∏ ∏ f (t) = ∏ f (t) d|n d d|n t| dn t|n ∑ µ(d) d| nt = ∏ f (t) = f (n) , t|n điều phải chứng minh. Ta có công thức trực tiếp tính Φn (X) như sau. Định lý 1.1.16. Cho n là một số nguyên dương. Khi đó Φn (X) = ∏(X n/d − 1)µ(d) . d|n Chứng minh. Suy ra từ Định lý 1.1.11 và Định lý 1.1.15. 1.2 Sơ lược về số nguyên đại số Định nghĩa 1.2.1. Số phức α được gọi là số nguyên đại số nếu tồn tại đa thức f (X) ∈ Z[X] với hệ số ứng với số mũ cao nhất bằng 1 mà f (α) = 0. Ký hiệu A là tập các số nguyên đại số. Ví dụ 1.2.2. (1) Mọi số nguyên là số nguyên đại số. (Trong bổ đề dưới đây ta sẽ chỉ ra, ngược lại nếu một số hữu tỷ và là số nguyên đại số thì nó phải là số nguyên.)
9 √ √ 1+ 5 1− 5 (2) và là số nguyên đại số, vì chúng là nghiệm của X 2 − 2 2 X − 1 = 0. (3) Số 1/2, π, . . . không phải số nguyên đại số. (Có vô hạn không đếm được số không phải là số nguyên đại số.) Ta có kết quả cơ bản nói rằng tổng và tích của hai số nguyên đại số là một số nguyên đại số. Tức là ta có kết quả sau. Định lý 1.2.3. Tập A cùng với 2 phép toán cộng và nhân thông thường lập thành một vành con của C. Ta cũng có kết quả sau. Bổ đề 1.2.4. Nếu một số hữu tỷ α là số nguyên đại số, thì α là số nguyên. Tức là ta có A ∩ Q = Z. a Chứng minh. Viết α = với gcd(a, b) = 1 và b ≥ 1. Vì α = a/b là số b nguyên đại số nên tồn tại a1 , . . . , an ∈ Z sao cho a a ( )n + a1 ( )n−1 + · · · + an = 0. b b Nhân cả hai về của phương trình trên với bn , ta được an + a1 an−1 b + · · · + an bn = 0. Giả sử b > 1. Khi đó gọi p là một ước nguyên tố của b. Ta có p chia hết −(a1 an−1 b + · · · + an bn ) = an . Do vậy p chia hết a. Điều này mâu thuẫn với việc ước chung lớn nhất của a và b là 1. Như vậy b = 1 và α = a là số nguyên.
10 Chương 2 Dãy hồi quy bậc hai Trong chương này chúng tôi trình bày về một số kiến thức về dãy hồi quy bậc hai, dãy Lucas và một số tính chất số học của dãy Lucas. Tài liệu tham khảo chính được sử dụng là [3]. 2.1 Định nghĩa Định nghĩa 2.1.1. Cho k ≥ 1 là một số nguyên. Một dãy (un )n≥0 ⊆ C gọi là hồi quy tuyến tính bậc k nếu với mọi n ≥ 0, ta có un+k = a1 un+k−1 + a2 un+k−2 + · · · + ak uk với dãy hệ số a1 , . . . , ak cho trước trong C. Chúng ta giả sử rằng ak 6= 0 (vì nếu không, các dãy (un )n≥0 sẽ là hồi quy tuyến tính với bậc nhỏ hơn k). Nếu a1 , . . . , ak ∈ Z và u1 , . . . , uk−1 ∈ Z thì theo quy nạp ta có, un là một số nguyên với mọi n ≥ 0. Đa thức f (X) = X k − a1 X k−1 − . . . − ak ∈ C [X] s được gọi là các đa thức đặc trưng của (un )n≥0 . Giả sử rằng f (X) = ∏ (X − αi )σi , i=1 ở đây α1, . . . , αs là những nghiệm riêng biệt của f (X) với bội σ1 , . . . , σs tương ứng. Mệnh đề 2.1.2. Giả sử rằng f (X) ∈ Z [X] có các nghiệm phân biêt. Khi k đó, tồn tại hằng số c1 , . . . , ck ∈ C sao cho un = ∑ ci αin , với ∀n ≥ 0. i=1
11 Chứng minh. Đặt u (z) = ∑ un z n . n≥0 Ta thấy u (z) (1 − a1 z − · · · − ak zk ) = u0 + (u1 − u0 a1 ) z + (u2 − u1 a1 − u2 a2 ) z2 + . . . + ∑ (um − a1um−1 − . . . − ak um−k ) zm =: P (z) , m≥k k−1 trong đó P (z) = ∑ (um − a1 um−1 − . . . − am u0 ) zm ∈ C [z] . Do đó, m=0 P (z) P (z) P (z) u (z) = k = k = k 1 − a1 z − . . . − ak z z f (1/z) zk ∏i=1 (1/z − αi ) k P (z) ci = k =∑ ∏i=1 (1 − zαi ) i=1 (1 − zαi ) với các hệ số ci ∈ K nào đó. Nếu n o −1 |z| < ρ := min |αi | : i = 1, . . . ., k , thì ta có thể viết 1 = ∑ (zαi )n = ∑ αin zn , ∀n ≥ 0. 1 − zαi n≥0 n≥0 Như vậy, với |z| < ρ ta có ! k k ∑ unzn = u (z) = ∑ ci ∑ αinzn = ∑ ∑ ciαin zn n≥0 i=1 n≥0 n≥0 i=1 So sánh hệ số, ta có điều phải chứng minh. Khi k = 2, dãy (un )n≥0 được gọi là hồi quy bậc hai. Trong trường hợp này, đa thức đặc trưng của nó có dạng f (X) = X 2 − a1 X − a2 = (X − α1 ) (X − α2 ) .
12 Giả sử rằng α1 6= α2 . Từ Mệnh đề 2.1.2 ta có un = c1 α1n + c2 α2n , ∀n ≥ 0. (1) Định nghĩa 2.1.3. Một dãy hồi quy bậc hai (un )n≥0 với số hạng tổng quát cho bởi công thức ở trên được gọi là không suy biến nếu c1 c2 α1 α2 6= 0 và α1 /α2 không là căn bậc hai của 1. 2.2 Một số ví dụ về dãy hồi quy bậc hai 2.2.1 Dãy Fibonacci Dãy Fibonacci là dãy cho bởi F0 = 0, F1 = 1 và Fn+2 = Fn+1 + Fn , ∀n ≥ 0. Đa thức đặc trưng của dãy này là f (X) = X 2 − X − 1 = (X − α) (X − β ) , √ √ với α = (1 + 5)/2 và β = (1 − 5)/2. Ta tìm c1 và c2 nhờ công thức (1). Chúng ta cho n các giá trị 0 và 1 và có được hệ c1 + c2 = F0 = 0, c1 α + c2 β = F1 = 1. √ √ √ Giải hệ, ta được c1 = 1/ 5, c2 = −1/ 5. Vì 5 = (α − β ), ta có thể viết αn − β n Fn = với mọi n ≥ 0. α −β 2.2.2 Dãy Mersenne Dãy Mersenne là dãy cho bởi M0 = 0, M1 = 1 và Mn+2 = 3Mn+1 − 2Mn , với mọi n ≥ 0. Đa thức đặc trưng của dãy này là f (X) = X 2 − 3X + 2 = (X − 2)(X − 1). Và Mn = c1 2n + c2 , ∀n, với c1 , c2 ∈ C nào đó. Ta tìm c1 và c2 bằng cách cho n các giá trị 0 và 1 và có được hệ c1 + c2 = M0 = 0, 2c1 + c2 = M1 = 1.
13 Giải hệ, ta được c1 = 1, c2 = −1. Ta có thể viết Mn = 2n − 1, ∀n ≥ 0. 2.3 Dãy Lucas 2.3.1 Định nghĩa và ví dụ Định nghĩa 2.3.1. Một dãy hồi quy bậc hai (un )n≥0 với u0 = 0, u1 = 1 và a1 , a2 là hai số nguyên nguyên tố cùng nhau, được gọi là một dãy Lucas. Nếu α1 và α2 là các nghiệm của phương trình đặc trưng, thì ta có thể kiểm tra một cách dễ dàng với một dãy Lucas (un )n≥0 công thức (1) được viết lại là α n − α2n un = 1 , ∀n ≥ 0. α1 − α2 Ví dụ 2.3.2. Các dãy Fibonacci (Fn )n≥0 và dãy Mersenne (Mn )n≥0 là các dãy Lucas. 2.3.2 Ước nguyên tố của số hạng trong dãy Lucas Trong phần này, dãy (un )n≥0 là một dãy Lucas. Định nghĩa 2.3.3. Nếu a là một số nguyên và p là một số nguyên tố lẻ, khi đó ký hiệu Legendre (a|p) được định nghĩa là (i) (a|p) = 0 nếu p|a; (ii) (a|p) = 1 nếu p /| a, và tồn tại một số nguyên x sao cho x2 ≡ a( mod p); (iii) (a|p) = −1 nếu là trường hợp còn lại. Ta đặt ∆ = (α1 − α2 )2 . Chúng ta nhắc lại rằng một số nguyên đại số là một số phức mà là nghiệm của một đa thức monic với hệ số nguyên. Các số nguyên là số nguyên đại số. Tổng và tích của các số nguyên đại số cũng là số nguyên đại số. Một số hữu tỉ đồng thời số nguyên đại số thì phải là số nguyên. Nếu m là một số nguyên và α là một số nguyên đại số, chúng ta nói rằng m chia hết α nếu α/m là một số nguyên đại số. Định lý 2.3.4. Cho p là một số nguyên tố. Chúng ta có các tính chất sau (i) Nếu p | a2 thì p - un với mọi n ≥ 1;
14 (ii) Nếu p | ∆, thì p | u p ; (iii) Nếu p - ∆a2 và (∆|p) = 1, thì p | u p−1 ; (iv) Nếu p là một số nguyên tố lẻ, p - ∆a2 và (∆|p) = −1, thì p | u p+1 . Chứng minh. (i) Giả sử rằng p | un đối với số n > 0 nào đó. Cho n là nhỏ nhất thỏa mãn điều này. Rõ ràng là n ≥ 2 vì u1 = 1. Vì un = a1 un−1 + a2 un−2 , và p | a2 , ta suy ra p | a1 un−1 . Vì gcd (a1 , a2 ) = 1 và p | a2 , nên p - a1 . Do vây p | un−1 , mâu thuẫn với cách chọn n. (ii) Đầu tiên ta giả sử là p = 2. Vì p | ∆ = a21 + 4a2 , nên a1 chẵn. Như vậy, 2 | a1 = u2 . Bây giờ chúng ta giả sử rằng p > 2. Đặt √ √ a1 + ∆ a1 − ∆ α1 = và α2 = . 2 2 Khi đó √ !p √ !p a 1 + ∆ a 1 − ∆ α1p − α2p = − 2 2 √ 2 ∆ p p−1 p p−3 (p−1)/2 = p a + a ∆+···+∆ . 2 1 1 3 1 √ Vì ∆ = α1 − α2 , nên (p−1)/2 p−1 p p−(2k+1) k 2 up = ∑ a1 ∆. k=0 2k + 1 Vì p|∆, nên phía bên tay phải của biểu thức trên là một bội số của p. Do vậy, p | 2 p−1 u p . Và vì p lẻ, chúng ta suy ra rằng p | u p . (iii) và (iv). Ta có √ !p p ! a1 + ∆ 1 p p−k k/2 α1p = = p a1p + ∑ a1 ∆ . 2 2 k=1 k
15 √ Do vậy, 2 p α1p ≡ a1p +∆(p−1)/2 ∆ ( mod p). Giả sử (∆|p) = 1. Khi đó ∆(p−1)/2 ≡ 1 ( mod p), và ta có 2 p α1p ≡ 2α1 ( mod p). Vì p là số lẻ và 2 p ≡ 2 ( mod p), nên ta suy ra α1p ≡ α1 ( mod p). Do đó, α1p ≡ α1 ( mod p) và α1p+1 ≡ α12 ( mod p) . Ta cũng thu được các đồng dư tương tự khi thay α1 bởi α2 . Trừ những đồng dư này ta được (α1 − α2 )(u p − 1) ≡ 0 (mod p) và (α1 − α2 )(u p+1 − u2 ) ≡ 0 ( mod p) . Nói riêng, p | ∆ (u p − 1) và p | ∆ (u p+1 − u2 ). Vì p - ∆, ta suy ra u p+1 ≡ u2 (mod p) và u p ≡ 1 ( mod p). Từ u p+1 = a1 u p + a2 u p−1 , lấy modulo theo p ta suy ra u2 ≡ a1 + a2 u p−1 ( mod p). Vì u2 = a1 , nên ta có p | a2 u p−1 . Do p - a2 , nên ta có p | u p−1 , điều phải chứng minh. Trong trường hợp khi (∆|p) = −1, thì ta có √ 2 p α1 ≡ a1 − ∆ ≡ 2α2 ( mod p) . Do đó α1p = α2 ( mod p). Điều này suy ra α1p+1 ≡ α1 α2 ( mod p) ≡ −a2 ( mod p). Lập luận tương tự ta có α2p+1 ≡ −a2 ( mod p). Trừ hai đồng dư này cho nhau, ta được α1p+1 − α2p+1 ≡ 0 ( mod p). Như vậy, p | ∆u p+1 , và do đó p | u p+1 vì p - ∆. Ví dụ 2.3.5. Đối với các dãy Fibonacci (Fn )n≥0 ta có ∆ = (α − β )2 = 5. Nếu p = 13, thì 13 | F14 vì (5|13) = (13|5) = (3|5) = −1. Thực tế, F14 = 377 = 13 · 29. Mệnh đề 2.3.6. Với mọi số nguyên dương m và n, ta có gcd (um , un ) = ugcd(m,n) . Chứng minh. Nếu m | n, thì bằng cách viết n = ml, ta có un α1n − α2m (α1m )l − (α2m )l = m m = m m = (α1m )l−1 + (α1m )l−2 α2m + · · · + (α2m )l−1 . u m α1 − α2 α1 − α2
16 Vế trái của công thức trên là một số hữu tỷ, và vế phải là một số nguyên đại số vì nó là một đa thức với hệ số nguyên của các số nguyên đại số α1 và α2 . Như vậy, số này là một số nguyên. Ta kết luận rằng nếu m | n, thì um | un . Bây giờ, ta gọi d = gcd(m, n). Vì d | m, nên ud | um . Tương tự, ta có ud | un . Do vậy ud | gcd(um , un ). Ngược lại, đầu tiên ta giả sử rằng m và n nguyên tố cùng nhau. Bằng quy nạp theo max{m, n}, ta chứng minh được rằng tồn tại hai đa thức P(x) và Q(x) với hệ số nguyên sao cho xm − 1 xn − 1 P (x) + Q (x) = 1. x−1 x−1 Thật vậy, nếu m = n = 1, ta có thể lấy P(x) = 1 và Q(x) = 0. Nếu m > n ≥ 1, thì ta viết m = nq + r với với 1 ≤ r < n, và sử dụng đồng nhất thức xm − 1 xn − 1 xnq − 1 r xr − 1 − x = . x−1 x−1 xn − 1 x−1 Theo giả thiết quy nạp, tồn tại P1 (x) , Q1 (x) ∈ Z [x] sao cho xn − 1 xr − 1 P1 (x) + Q1 (x) = 1. x−1 x−1 Do vậy xn − 1 m x − 1 xn − 1 xnq − 1 r 1= P1 (x) + − x Q1 (x) x−1 x−1 x − 1 xn − 1 xm − 1 xn − 1 = P (x) + Q (x) . x−1 x−1 Với P (x) := Q1 (x) và Q (x) := P1 (x) − ((xnq − 1) / (xn − 1)) xr Q1 (x). Bây giờ, với hai số nguyên dương tùy ý m và n, ta viết m = dm1 và n = dn1 với d = gcd(m, n). Khi đó tồn tại P(x), Q(x) ∈ Z[x] sao cho xm1 − 1 xn1 − 1 P (x) + Q (x) = 1. x−1 x−1
17 Ta thay x bởi xd và nhận được xm − 1 d xn − 1 d xd − 1 P x + Q x = . x−1 x−1 x−1 Thuần nhất hóa hai vế của đẳng thức này, ta nhận được x m − ym x n − yn xd − yd D−d R (x, y) + S (x, y) = ( )y , x−y x−y x−y trong đó R (x, y) , S (x, y) ∈ Z [x, y] là các thuần nhất hóa của P(xd ), và Q(xd ) tương ứng, và D là bậc của đa thức (xm − 1)P(xd )/(x − 1). Nhắc lại rằng nếu f (x) = c0 xk + c1 xk−1 + · · · + ck ∈ C [x] , thì thuần nhất hóa của nó là f (x, y) = c0 xk + c1 xk−1 y + . . . + ck yk ∈ C [x, y] . Thay (x, y) := (α1 , α2 ), ta nhận được um R (α1 , α2 ) + un S (α1 , α2 ) = ud α2D−d . Do đó, ud α2D−d um un = R (α1 , α2 ) + S (α1 , α2 ) gcd (um , un ) gcd (um , un ) gcd (um , un ) Trong biểu thức trên, vế phải là một số nguyên đại số. Do đó, vế trái cũng (D−d) là một số nguyên đại số. Do vậy gcd(um , un ) | ud α2 . Tương tự, ta cũng (D−d) có gcd(um , un ) | ud α1 . Như vậy, gcd (um , un )2 chia hết u2d (α1 α2 )D−d = ±u2d (α2 )D−d . Vì không có ước nguyên tố nào của a2 chia hết ud (theo Định lý 2.3.4 (i)), nên gcd(um , un )2 chia hết u2d . Do vậy gcd (um , un ) chia hết ud , và ta hoàn thành chứng minh. un Bổ đề 2.3.7. Nếu m | n và p là số nguyên tố sao cho p | gcd(um , ), thì um n p| . m