Luận văn Dãy hồi quy bậc hai

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. Chứng minh. Viết α = a b với gcd(a,b) = 1 và b ≥ 1. Vì α = a/b là số nguyên đại số nên tồn tại a1, . . . ,an ∈ Z sao cho ( a b )n+a1( a b )n−1+ · · ·+an = 0. Nhân cả hai về của phương trình trên với bn, ta được an+a1an−1b+ · · ·+anbn = 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 −(a1an−1b+ · · ·+ anbn) = 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 = a1un+k−1+a2un+k−2+ · · ·+akuk 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) = Xk−a1Xk−1− . . .−ak ∈ C [X ] được gọi là các đa thức đặc trưng của (un)n≥0. Giả sử rằng f (X)= s ∏ i=1 (X−αi)σi, ở đâ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 đó, tồn tại hằng số c1, . . . ,ck ∈ C sao cho un = k ∑ i=1 ciαni , với ∀n≥ 0. 11 Chứng minh. Đặt u(z) = ∑ n≥0 unzn. Ta thấy u(z)(1−a1z−·· ·−akzk) = u0+(u1−u0a1)z+(u2−u1a1−u2a2)z2+ . . . + ∑ m≥k (um−a1um−1− . . .−akum−k)zm =: P(z) , trong đó P(z) = k−1 ∑ m=0 (um−a1um−1− . . .−amu0)zm ∈ C [z] . Do đó, u(z) = P(z) 1−a1z− . . .−akzk = P(z) zk f (1/z) = P(z) zk∏ki=1(1/z−αi) = P(z) ∏ki=1 (1− zαi) = k ∑ i=1 ci (1− zαi) với các hệ số ci ∈ K nào đó. Nếu |z|< ρ := min { |αi|−1 : i= 1, . . . .,k } , thì ta có thể viết 1 1− zαi = ∑n≥0 (zαi)n = ∑ n≥0 αni z n, ∀n≥ 0. Như vậy, với |z|< ρ ta có ∑ n≥0 unzn = u(z) = k ∑ i=1 ci∑ n≥0 αni z n = ∑ n≥0 ( k ∑ i=1 ciαni ) zn 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) = X2−a1X−a2 = (X−α1)(X−α2) . 12 Giả sử rằng α1 6= α2. Từ Mệnh đề 2.1.2 ta có un = c1αn1 + c2α n 2 , ∀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 c1c2α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) = X2−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 Fn = αn−β n α−β với mọi n≥ 0. 2.2.2 Dãy Mersenne Dãy Mersenne là dãy cho bởiM0 = 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) = X2−3X+2 = (X−2)(X−1). VàMn = c12n+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à un = αn1 −αn2 α1−α2 , ∀n≥ 0. 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 | up; (iii) Nếu p - ∆a2 và (∆|p) = 1, thì p | up−1; (iv) Nếu p là một số nguyên tố lẻ, p - ∆a2 và (∆|p) =−1, thì p | up+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 = a1un−1+a2un−2, và p | a2, ta suy ra p | a1un−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 α1 = a1+ √ ∆ 2 và α2 = a1− √ ∆ 2 . Khi đó α p1 −α p2 = ( a1+ √ ∆ 2 )p − ( a1− √ ∆ 2 )p = 2 √ ∆ 2p (( p 1 ) ap−11 + ( p 3 ) ap−31 ∆+ · · ·+∆(p−1)/2 ) . Vì √ ∆= α1−α2, nên 2p−1up = (p−1)/2 ∑ k=0 ( p 2k+1 ) ap−(2k+1)1 ∆ k. 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 | 2p−1up. Và vì p lẻ, chúng ta suy ra rằng p | up. (iii) và (iv). Ta có α p1 = ( a1+ √ ∆ 2 )p = 1 2p ( ap1 + p ∑ k=1 ( p k ) ap−k1 ∆ k/2 ) . 15 Do vậy, 2pα p1 ≡ ap1+∆(p−1)/2 √ ∆(mod p). Giả sử (∆|p)= 1. Khi đó ∆(p−1)/2≡ 1(mod p), và ta có 2pα p1 ≡ 2α1 (mod p). Vì p là số lẻ và 2p ≡ 2(mod p), nên ta suy ra α p1 ≡ α1 (mod p). Do đó, α p1 ≡ α1 (mod p) và α p+11 ≡ α21 (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)(up−1)≡ 0 (mod p) và (α1−α2)(up+1−u2)≡ 0(mod p) . Nói riêng, p | ∆(up−1) và p | ∆(up+1−u2). Vì p - ∆, ta suy ra up+1 ≡ u2 (mod p) và up ≡ 1(mod p). Từ up+1 = a1up+ a2up−1, lấy modulo theo p ta suy ra u2 ≡ a1+ a2up−1 (mod p). Vì u2 = a1, nên ta có p | a2up−1 . Do p - a2, nên ta có p | up−1, điều phải chứng minh. Trong trường hợp khi (∆|p) =−1, thì ta có 2pα1 ≡ a1− √ ∆≡ 2α2 (mod p) . Do đó α p1 =α2 (mod p). Điều này suy ra α p+1 1 ≡α1α2 (mod p)≡−a2 (mod p). Lập luận tương tự ta có α p+12 ≡−a2 (mod p). Trừ hai đồng dư này cho nhau, ta được α p+11 −α p+12 ≡ 0(mod p). Như vậy, p | ∆up+1, và do đó p | up+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 um = αn1 −αm2 αm1 −αm2 = (αm1 ) l− (αm2 )l αm1 −αm2 = (αm1 ) l−1+(αm1 ) l−2αm2 + · · ·+(αm2 )l−1. 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ố α1và α2. Như vậy, số này là một số nguyên. Ta kết luận rằng nếum | 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 x−1 P(x)+ xn−1 x−1 Q(x) = 1. Thật vậy, nếum= n= 1, ta có thể lấy P(x) = 1 vàQ(x) = 0. Nếum> 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 x−1 − xn−1 x−1 ( xnq−1 xn−1 ) xr = xr−1 x−1 . Theo giả thiết quy nạp, tồn tại P1 (x) ,Q1 (x) ∈ Z [x] sao cho xn−1 x−1 P1 (x)+ xr−1 x−1 Q1 (x) = 1. Do vậy 1 = xn−1 x−1 P1 (x)+ ( xm−1 x−1 − xn−1 x−1 ( xnq−1 xn−1 ) xr ) Q1 (x) = xm−1 x−1 P(x)+ xn−1 x−1 Q(x) . Với P(x) := Q1 (x) và Q(x) := P1 (x)− ((xnq−1)/(xn−1))xrQ1 (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 x−1 P(x)+ xn1−1 x−1 Q(x) = 1. 17 Ta thay x bởi xd và nhận được xm−1 x−1 P ( xd ) + xn−1 x−1 Q ( xd ) = xd−1 x−1 . Thuần nhất hóa hai vế của đẳng thức này, ta nhận được xm− ym x− y R(x,y)+ xn− yn x− y S (x,y) = ( xd− yd x− y )y D−d, 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) = c0xk+ c1xk−1+ · · ·+ ck ∈ C [x] , thì thuần nhất hóa của nó là f (x,y) = c0xk+ c1xk−1y+ . . .+ ckyk ∈ C [x,y] . Thay (x,y) := (α1,α2), ta nhận được umR(α1,α2)+unS (α1,α2) = udαD−d2 . Do đó, udαD−d2 gcd(um,un) = um gcd(um,un) R(α1,α2)+ un gcd(um,un) S (α1,α2) Trong biểu thức trên, vế phải là một số nguyên đại số. Do đó, vế trái cũng là một số nguyên đại số. Do vậy gcd(um,un) | udα(D−d)2 . Tương tự, ta cũng có gcd(um,un) | udα(D−d)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. Bổ đề 2.3.7. Nếu m | n và p là số nguyên tố sao cho p | gcd(um, unum ), thì p | n m . 18 Chứng minh. Vì p | um, nên αm1 ≡ αm2 (modp). Ta viết n=ml. Khi đó ta có un um = (αm1 ) l− (αm2 )l αm1 −αm2 = (αm1 ) l−1+ · · ·+(αm2 )l−1. Vì αm1 ≡ αm2 (mod p), và p | un um , nên p | l(αm1 )l−1 và p | l(αm2 )l−1. Như vậy, p | l2(α1α2)m(l−1). Vì α1α2 = −a2, ta có p | la2. Nhưng p - a2 (theo Định lý 2.3.4 (i)), do đó p | l. Bổ đề 2.3.8. 1. Nếu p> 2 là số nguyên tố và p | un, thì p ‖ unpun . 2. Nếu p= 2 và 2 | un, thì 2 | u2nun . Hơn nữa nếu 4 | un thì 2 ‖ u2n un . Chứng minh. (i) Vì p|αn1 −αn2 , ta có thể viết αn1 = αn2 + pλ với λ là một số nguyên đại số. Khi đó unp un = αnp1 −αnp2 αn1 −αn2 = (αn1 ) p−1+ · · ·+(αn2 )p−1 = (αn2 + pλ ) p−1+(αn2 + pλ ) p−2αn2 + · · ·+(αn2 )p−1 = ((αn2 ) p−1+(p−1)p(αn2 )p−2λ )+((αn2 )p−1+(p−2)p(αn2 )p−2λ ) + · · ·+(αn2 )p−1+ p2γ = p(αn2 ) p−1+ p(αn2 ) p−2λ ((p−1)+(p−2)+ · · ·+0)+ p2γ = pα(p−1)n2 + p2 (p−1) 2 αn(p−2)2 λ + p 2λ , ở đây γ là một số nguyên đại số. Do p lẻ nên upn pun ≡ α(p−1)n2 (mod p). Lập luận tương tự, ta có upn pun ≡ α(p−1)n1 (mod p). Nhân hai đồng dư trên, nhận được( upn pun )2 ≡±a(p−1)n2 (mod p). 19 Vì p - a2, nên p ‖ upnun . (ii) Ta giả sử p = 2. Khi đó ta có upn un = u2n un = vn = αn1 +α n 2 . Ta sẽ sử dụng công thức v2n−∆u2n = (αn1 +αn2 )2− (αn1 −αn2 )2 = 4(α1α2)n =±4an2. (12) Vì 2 | un, nên 2 | vn theo (12). Bây giờ ta giả sử 4 | un. Trước tiên ta chú ý rằng a2 là lẻ (theo Định lý 2.3.4 (i)). Từ (12) suy ra v2n = ∆u 2 n+±4an2 ≡ 4(mod 8). Do vậy 2 ‖ vn = u2nun . Định lý 2.3.9. Cho p là một số nguyên tố và pt ‖ um với t > 0. Cho q một số tự nhiên nguyên tố cùng nhau với p. Ta có các khẳng định sau. (i) Nếu pt 6= 2 thì pt+r ‖ umqpr . (ii) Nếu pt = 2 thì pt+r | umqpr . Chứng minh. Suy ra từ bổ đề trên và theo quy nạp theo r. 20 Chương 3 Định lý ước nguyên thủy Trong chương này chúng tôi 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, Định lý Zsigmondy liên quan và một số bài tập ứng dụng trong toán sơ cấp. 3.1 Định lý Carmichael Trong mục này, chúng tôi trình bày chứng minh Định lý Carmichael dựa chủ yếu theo hai tài liệu [6, 5]. Để thuận tiện chúng tôi sẽ sử dụng các ký hiệu theo hai tài liệu này. Nhắc lại rằng dãy (Dn) định nghĩa bởi Dn = (αn−β n)/(α−β ) là một dãy Lucas. Ở đây α và β là hai nghiệm phân biệt của phương trình đặc trưng f (x) = x2− Lx+M, với L và M là các số nguyên nguyên tố cùng nhau. Ta nói dãy (Dn) là thực nếu α và β là thực. Dễ thấy với mọi n thì Dn là số nguyên. Ta nói rằng một số nguyên tố p là ước nguyên thủy của Dn nếu p chia hết Dn nhưng không chia hết Dm với mọi 0 <m< n. (Ta có định nghĩa tương tự cho mọi dãy gồm các số nguyên (En).) Năm 1913, Carmichael [1] đã chứng minh kết quả sau. Định lý 3.1.1 (Carmichael). Nếu α và β là các số thực và n 6= 1,2,6 thì Dn có một ước nguyên thủy trừ trường hợp Dn = F12, số hạng thứ 12 trong dãy Fibonacci. 21 3.1.1 Một điều kiện đủ về tồn tại ước nguyên thủy Định nghĩa 3.1.2. Cho {Dn} là dãy Lucas thực với α,β là các nghiệm thực của đa thức đặc trưng của nó. Ta định nghĩa các số chia đường tròn liên kết với Dn như sau Q1 = Q1(α,β ) = 1, Qn = Qn(α,β ) = ∏ 1≤r≤n (r,n)=1 (α− e2piir/nβ ) = βϕ(n)Φn(αβ ), với n≥ 2. Bổ đề 3.1.3. Với mọi n≥ 1, ta có (i) Dn =∏d|nQd. (ii) Qn ∈ Z. (iii) Số nguyên tố p là ước nguyên thủy của Dn khi và chỉ khi nó là ước nguyên thủy của Qn. Chứng minh. (i) Ta có (α−β )Dn = αn−β n = β n (( α β )n −1 ) = β n∏ d|n Φd( α β ) =∏ d|n βϕ(d)Φd( α β ) = (α−β )∏ d|n Qd, theo Định lý 1.1.16 và chú ý rằng Q1 = 1. (ii) Ta chỉ cần chứng minh Qn ∈Q và Qn ∈ A, vì ta biết Q∩A= Z. Ta chứng minh Qn ∈ Q \ {0} bằng quy nạp theo n. Theo định nghĩa Q1 = 1 và Q2 = α + β = L là số hữu tỷ khác 0. Giả sử rằng n > 2 và Qk ∈Q\{0} với mọi k < n. Theo (i), ta có Qn = Dn ∏ d|n,d<n Qd . Do vậyQn ∈Q. Ta chỉ raDn 6= 0. Giả sửDn= 0= α n−β n α−β . Suy ra α n= β n. Vì α 6= β nên α = −β (chú ý rằng α và β là các số thực). Điều này mâu thuẫn với L= α+β 6= 0. Do vậy Qn ∈Q\{0}. 22 Từ định nghĩa củaQn, ta suy raQn là số nguyên đại số vì α,β ,e2pii/n ∈A và A là một vành. (iii) Giả sử p là một ước nguyên thủy của Dn. Vì Qd | Dd theo (i), nên p -Qd với mọi d < n. Do đó p |Qn vì p |Dn =∏d|nQd. Do đó p là một ước nguyên thủy của Qn. Ngược lại, giả sử p là một ước nguyên thủy của Qn. Khi đó p | Dn vì Qn | Dn. Giả sử p | Dm đối với m < n nào đó. Khi đó p | Qd, với d | m nào đó (theo (i)-(ii)). Nhưng hiển nhiên ta có d ≤ m < n. Điều này mâu thuẩn với giả sử p là ước nguyên thủy của Qn. Định nghĩa 3.1.4. Ta định nghĩa hạng của một số nguyên tố p trong dãy Lucas {Dn} là số nguyên dương k nhỏ nhất sao cho p | Dk. Nếu không tồn tại k > 0 như vậy, ta nói p có hạng 0. Bổ đề 3.1.5. Nếu p có hạng k > 0, thì p | Dn khi và chỉ khi k | n. Chứng minh. Giả sử p | Dn. Gọi d = gcd(k,n). Khi đó gcd(Dk,Dn) = Dd (theo Mệnh đề 2.3.6). Vì p | Dk và p | Dn, nên p | Dd. Do vậy k ≤ d, vì k là hạng của p. Kết hợp với việc d = gcd(k,n), ta suy ra d = k và k | n. Ngược lại, giả sử k | n, khi đó ta có Dk | Dn (theo Mệnh đề 2.3.6). Do vậy p | Dn. Bổ đề 3.1.6. Giả sử p có hạng k > 0 trong {Dn}. Khi đó nếu p | Qn thì n= kpr với r ≥ 0 nào đó. Chứng minh. Theo Bổ đề 3.1.3 (i), ta có p | Dn. Do vậy theo Bổ đề 3.1.5, ta có k | n. Như vậy n = kprq, với gcd(q, p) = 1 và r ≥ 0. Đặt m = kpr. Ta có p | Dk | Dm. Từ Bổ đề 2.3.7, ta suy ra p - DnDm . (Vì giả sử ngược lại thì ta sẽ có p | gcd(Dm, DnDm ), và p sẽ chia hết n/m= q, vô lý.) Lại sử dụng Bổ đề 3.1.3 (i), ta suy ra q= 1. Bổ đề 3.1.7. Cho p nguyên tố và giả sử p có hạng k > 0 trong {Dn}. Nếu n 6= 1,2,6 và nếu p chia hết Qn và Qm với 0 < m< n, thì n= prk với r ≥ 1 và p ‖ Qn. Chứng minh. Theo Bổ đề 3.1.6, ta có m = psk và n = prk với 0 ≤ r,s. Vì m s≥ 0. Suy ra r ≥ 1. Theo Bổ đề 2.3.8 và theo quy nạp theo r, ta có pr | Dkpr−1 vì p | Dk. Ta xét hai trường hợp. 23 Trường hợp 1: pr 6= 2. Ta viết k = k′pu với gcd(k′, p) = 1. Khi đó theo Bổ đề 2.3.8, ta có p ‖ Dkpr Dkpr−1 =∏ d|k′ Qdpr+u. Do vậy p ‖Qdpr+u với d | k′ nào đó. Khi đó theo Bổ đề 3.1.6, ta có k | dpr+u. Do vậy k′ | d, và ta suy ra d = k′. Khi đó p ‖ Qk′pr+u = Qn. Trường hợp 2: pr = 2, tức là p = 2 và r = 1. Từ Định lý 2.3.4 (i), ta suy ra M lẻ (vì 2 | Dk). Nếu L là lẻ thì ta suy ra 2 - D2 = L và 2 | D3 = α2 +αβ + β 2 = (α + β )2−αβ = L2−M. Khi đó k = 3 và n = 6, mâu thuẫn với giả thiết n 6= 6. Như vậy ta có L chẵn. Ta suy ra 2 | D2 = L, và do vậy k = 2. Ta có Qn = Q4 = α2+β 2 = (α+β )2−2αβ = L2−2M. Do L là chẵn và M lẻ nên 2 ‖ Q4, điều phải chứng minh. Bây giờ, giả sử rằng n được phân tích thành tích các lũy thừa nguyên tố n = pe11 p e2 2 . . . p el l , với p1, p2, . . . , pl là các số nguyên số phân biệt, và e1, . . . ,el là các số nguyên dương. Bổ đề 3.1.8. Cho n 6= 1,2,6. Một điều kiện đủ để Dn chứa ít nhất một ước nguyên thủy là |Qn|> p1p2. . . pl. Chứng minh. Ta chứng minh bằng phản chứng. Giả sử rằng Dn không có ước nguyên thủy. Khi đó Qn không có ước nguyên thủy (theo Bổ đề 3.1.3 (iii)). Nếu p là một ước nguyên tố tùy ý của Qn, thì p chia hết một Qm nào đó với 0 < m < n. Do đó, p | n và p ‖ Qn (theo Bổ đề 3.1.7). (Chú ý rằng p | Qn | Dn, nên p có hạng khác không trong {Dn}.) Do đó, Qn chia hết p1p2 . . . pl nên |Qn| ≤ p1p2 . . . pl. Bổ đề 3.1.9. Cho {Dn} là dãy Lucas thực với đa thức đặc trưng X2−LX+ M. Khi đó, với mọi n> 2, ta có Qn = ∏ (r,n)=1;0<r<n/2 (L2−Mθr), ở đây θr = 2+ζ r+ζ−r. 24 Chứng minh. Cố định n> 2. Ta có Qn = Qn(α,β ) = ∏ (r,n)=1;0<r<n/2 (α−ζ rβ )(α−ζ−rβ ) = ∏ (r,n)=1;0<r<n/2 ((α2+β 2)−α(2+ζ r+ζ−r)) = ∏ (r,n)=1;0<r<n/2 (L2−Mθr). Điều này suy ra từ ζ−r = ζ n−r; và với mọi 0 < r < n/2 thì n/2 < n− r < n và gcd(n− r,n) = gcd(r,n). Ta cố định số nguyên dương n > 2. Khi đó ta có thể coi Qn như là một hàm theo L và M. Ta sẽ xác định các giá trị L và M mà tại đó Qn nhận giá trị cực tiểu. Bổ đề 3.1.10. Cho n > 2 là một số nguyên cố định tùy ý. Nếu α ,β là số thực, thì Qn có giá trị bé nhất hoặc là khi L= 1 vàM =−1 hoặc khi L= 3 và M = 2. Chứng minh. Cố định một r mà 0 < r< n/2 và (r,n) = 1. Khi đó ζ r không là số thực. Do đó 0 < θr < 4. Khi M < 0, ta có L2−Mθr ≥ 1+θr, dấu bằng xảy ra chỉ trong trường hợp L= 1,M =−1. Khi M > 0, ta xem xét hai trường hợp M = 1 và M > 1. Trong trường hợp đầu tiên ta có L2 ≥ 4M+1, vì thế L2−Mθr ≥ 9−θr > 9−2θr. Bây giờ ta trường hợp M > 1. Vì L2 ≥ 4M+1, nên ta có L2−Mθr ≥ 4M+1−Mθr = 9−2θr+(M−2)(4−θr)≥ 9−2θr, . với dấu bằng chỉ xảy ra trong trường hợp M = 2,L = 3. Chú ý rằng 1+θr và 9−2θr đều dương. Khẳng định của bổ đề suy ra từ Bổ đề 3.1.9. 25 3.1.2 Chứng minh Định lý Carmichael Trong mục này ta sẽ đưa chứng minh Định lý Carmichael cho dãy Lucas thực tùy ý về việc kiểm tra định lý cho 2 trường hợp riêng: cho dãy Fi- bonacci và dãy Mersenne. Sau đó ta sẽ chứng minh Định lý Carmichael cho dãy Fibonacci và dãyMersenne, và kết thúc chứngminh Định lý Carmichael. Bổ đề 3.1.11. Nếu N > 2 và a là số thực mà |a|< 1 2 , thì Φn(a)≥ 1−|a|− |a|2. Chứng minh. Theo công thức nghịch đảo Mo¨bius, ta có Φn(X) =∏ d|n (Xd−1)µ(n/d) =∏ d|n (Xn/d−1)µ(d) =∏ d|n (1−Xn/d)µ(d). Ở đây đẳng thức cuối cùng suy ra từ việc n có một số chẵn các ước d mà µ(d) 6= 0. (Nếu l là số các ước nguyên tố của n, thì n có 2l ước số tự do-bình phương.) Do vậy, ta có Φn(a) =∏ d|n (1−a nd )µ(d). Khẳng định 1: (1−a nd )µ(d) ≥ 1−|a| nd . Chứng minh Khẳng định 1. Khi µ(d) = 0 hoặc 1, thì Khẳng định 1 là hiển nhiên. Giả sử µ(d) =−1. Nếu a≥ 0 thì 1≥ (1−|a|n/d)2 = (1−|a|n/d)(1− an/d), và từ đó suy ra Khẳng định 1. Nếu a< 0 và n/d lẻ, thì 1≥ 1− (|a|n/d)2 = (1−|a|n/d)(1+ |a|n/d) = (1−|a|n/d)(1−an/d), và từ đó suy ra Khẳng định 1. Nếu a< 0 và n/d chẵn, thì 1≥ (1−|a|n/d)2 = (1−|a|n/d)(1−an/d), và từ đó suy ra Khẳng định 1. 26 Từ các kết quả trên, ta suy ra Φn(a)≥∏ d|n (1−|a|n/d)≥ ∞ ∏ i=1 (1−|a|i). Khẳng định 2: Nếu 0 < x< 1/2 thì N ∏ i=2 (1−xi)≥ 1−x2−x3−·· ·−xN , với mọi N ≥ 2. Chứng minh Khẳng định 2. Ta chứng minh bằng quy nạp theo N = 2. Trường hợp N = 2 là hiển nhiên. Giả sử Khẳng định 2 đúng với N ≥ 2. Ta có (1− x2) · · ·(1− xN)(1− xN+1)≥ (1− x2−·· ·− xN)(1− xN+1) = 1− x2−·· ·− xN− xN+1 +(x2+ · · ·+ xN)(xN+1) ≥ 1− x2−·· ·− xN− xN+1. Khẳng định 2 được chứng minh. Do vậy, Khẳng định 2 suy ra Φn(a)≥ (1−|a|) ∞ ∏ i=2 (1−|a|i) ≥ (1−|a|)(1−|a|2−|a|3−·· ·) = (1−|a|)(1− |a| 2 1−|a|2 ) = 1−|a|− |a|2. Định lý 3.1.12. Nếu n 6= 1,2,3,5,6,12 thì Qn > p1p2 . . . pl đối với dãy Fi- bonacci. Chứng minh. Nghiệm của đa thức đặc trưng z2− z−1 của dãy Fibonacci là α = (1+ √ 5)/2 và β = (1−√5)/2. Vì |β/α| = (3−√5)/2 < 1/2, nên theo Bổ đề 3.1.11 ta có Φn( β α )≥ 1−|β α |− |β α |2 = 2 √ 5−4 > 2/5. 27 Hơn nữa, vì α > 3/2, nên ta có Qn(α,β ) = αφ(n)Φn( β α )> ( 2 5 )( 3 2 )φ(n). Như vậy ta chỉ cần chỉ ra ( 2 5 )( 3 2 )φ(n) > p1p2 . . . pl. (*) Khẳng định: Nếu (25)( 3 2) φ(pe11 ) > 2p1 (**) thì (*) đúng. Chứng minh Khẳng định. Giả sử ta có (**). Vì φ(n) = φ(pe11 )φ(n/p e1 1 ) và φ(n/pe11 )≥ (p2−1) · · ·(pl−1), nên ta có ( 2 5 )( 3 2 )φ(n) ≥ ( ( 2 5 )( 3 2 )φ(p e1 1 ) )(p2−1)···(pl−1) > (2p1)(p2−1)(p3−1)···(pl−1). Nhận xét rằng tích của hữu hạn các số nguyên dương luôn lớn hơn hoặc bằng tổng của chúng trừ trường hợp dạng 1a˙ < 1+ a. Ta giả sử rằng hoặc là l > 3 hoặc là pk 6= 2 với mọi k > 1. Khi đó (2p1)(p2−1)(p3−1)···(pl−1) ≥ (2p1)(p2−1)+(p3−1)+···+(pl−1) > p1p2 · · · pl, vì p1 ≥ 2 và 2p−1 ≥ p vỏi mọi p. Bây giờ ta giả sử l = 2 và p2. Khi đó hiển nhiên (2p1)p2−1 = 2p1 = p1p2. Ta xét trường hợp cuối cùng là l = 3 và hoặc là p2 = 2 hoặc là p3 = 2. Không mất tổng quát ta giả sử p3 = 2. Khi đó p1, p2 ≥ 3. Ta có (2p1)(p2−1)(p3−1)···(pl−1) = (2p1)p2−1 = (p1p3)p2−1 > p1p2p3. Ở đây ta đã sử dụng bất đẳng thức rằng xm−1 >mx với mọi x≥ 6 và m≥ 3. Khẳng định hoàn toàn được chứng minh. Giả sử n có một ước nguyên tố lớn hơn 7. Không mất tổng quát, ta có thể giả sử p1 > 7. Khi đó, bằng cách khảo sát hàm số, ta có thể chứng mính 28 rằng (2/5)(3/2)x−1−2x> 0 với mọi x> 7. Do đó (2/5)(3/2)φ(p1) > 2p1. Điều này kéo theo (*) dúng với mọi n chia hết cho một ước nguyên tố lớn hơn 7. Tiếp theo, nhận xét rằng (**) đúng với pe11 = 2 4,33,52 và 72. Do vậy, (**) cũng đúng với các lũy thừa cao hơn của các số nguyên tố này. Như vậy ta chỉ còn kiểm tra Qn > p1p2 . . . pl với n có dạng n= 2a3b5c7d, với 0 ≤ a ≤ 3,0 ≤ b ≤ 2 và 0 ≤ c,d ≤ 1. Ta kiểm tra được rằng (*) đúng với n 6= 1,2,3,4,5,6,7,10,12,14,15,18,30. Nhưng Q2 = 1,Q3 = 2,Q4 = 3,Q5 = 5,Q6 = 4,Q7 = 13, Q10 = 11,Q12 = 6,Q14 = 29,Q15 = 61,Q18 = 19,Q30 = 31. Kiểm tra trực tiếp rằngQn > p1 . . . pl trừ trường hợp n= 1,2,3,5,6,12. Định lý 3.1.13. Nếu n 6= 1,2,6, thì Qn > p1p2 . . . pl đối với dãy Mersenne. Chứng minh. Nghiệm của đa thức đặc trưng z2−3z+2 của dãy Mersenne là α = 2,β = 1. Theo Bổ đề 3.1.11, ta có Φn( β α )≥ 1−|β α |− |β α |2 = 1 4 . Do đó, Qn = Qn(α,β ) = αφ(n)Φn( β α )≥ ( 1 4 ) 2φ(n). Bằng quy nạp, ta có thể chứngminh rằng h(x)= (1/4)2x−(2/5)(3/2)x> 0 đúng với mọi x≥ 2 nguyên. Do vậy, với mọi n> 2 ta có Qn ≥ (1/4)2φ(n) > (2/5)(3/2)φ(n). Như trong chứng minh của Định lý 3.1.11, ta thấy (2/5)(3/2)φ(n) > p1p2 . . . pl với mọi n 6= 1,2,3,4,5,6,7,10,12,14,15,18,30. Hơn nữa (1/4)2φ(n)> 29 p1p2 . . . pl với n= 7,14,15,18,30. Các trường hợp còn lại là Q1 = 1,Q2 = 3,Q3 = 7,Q4 = 5,Q5 = 31,Q6 = 3,Q10 = 11,Q12 = 13. Kiểm tra trực tiếp, ta thấy Qn > p1p2 . . . pl với n= 3,4,5,10,12. Chứng minh Định lý Carmichael. Theo hai định lý trước, Qn > p1p2 . . . pl cho cả hai dãy Fibonacci và dãy Merseenne và n 6= 1,2,3,5,6,12. Bổ đề 3.1.8 và 3.1.10 suy ra Dn có một ước nguyên thủy khi n 6= 1,2,3,5,6,12. Xét n= 3. Khi đó ta khẳng định rằng Q3 > 3 trừ khi L = 1,M =−1 và L= 1,M =−2. Thật vậy, ta có M < L2/4 . Do vậy Q3 = α2+αβ +β 2 = (α+β )2−αβ = L2−M > L2−L2/4 = (3/4)L2. Khi L> 1 thìQ3 > (3/4)L2≥ 3. Bây giờ xét L= 1, khi đó 1/4= L2/4>M. Q3 nhỏ nhất khi M = −1, trong trường hợp này Q3 = 2. Vẫn giữ nguyên L = 1, giảm M từ -1 xuống M = −2, ta có Q3 = 3. Khẳng định hoàn toàn được chứng minh. Như vậy, ngoài hai trường hợp L = 1,M = −1 và L = 1,M =−2 thì D3 có ước nguyên thủy theo Bổ đề 3.1.10. Hơn nữa, ta kiểm tra trực tiếp được rằng D3 có ước nguyên thủy trong hai trường hợp riêng ở trên. Xét n = 5. Khi đó Q5 = 5 cho dãy Fibonacci và Q5 = 31 > 5 cho dãy Mersenne. Do vậy Q5 > 5 cho mọi dãy Lucas trừ trường hợp dãy Lucas này là Fibonacci (theo Bổ đề 3.1.10). Do đó D5 có ước nguyên thủy khi dãy Lucas này khác dãy Fibonacci (theo Bổ đề 3.1.8). Kiểm tra trực tiếp được F5 có ước nguyên thủy là 5. Xét n = 12. Khi đó Q12 = 6 cho dãy Fibonacci và Q12 = 31 cho dãy Mersenne. Do vậy Q12 > 6 cho mọi dãy Lucas trừ trường hợp dãy Lucas này là Fibonacci (theo Bổ đề 3.1.10). Do đó D12 có ước nguyên thủy khi dãy Lucas này khác dãy Fibonacci (theo Bổ đề 3.1.8). 3.2 Định lý Zsigmondy Định lý 3.2.1. Cho a,b ∈ N với gcd(a,b) = 1, và số tự nhiên n≥ 2. Khi đó lu