Dãy Lucas

Bách khoa toàn thư mở Wikipedia

Trong toán học, dãy Lucas là các dãy số nguyên đệ quy không đổi thỏa mãn hệ thức truy hồi

với là các số nguyên cho trước. Bất kỳ dãy số nào thỏa mãn hệ thức truy hồi này có thể được biểu diễn dưới dạng tổ hợp tuyến tính các dãy Lucas .

Nói chung, dãy Lucas biểu diễn dãy đa thức hệ số nguyên với biến .

Các ví dụ nổi tiếng về dãy Lucas gồm dãy Fibonacci, số nguyên tố Mersenne, số Pell, số Lucas, số Jacobsthal và tập siêu số Fermat. Các dãy Lucas được đặt theo tên nhà toán học Pháp Édouard Lucas.

Hệ thức truy hồi[sửa | sửa mã nguồn]

Cho hai tham số nguyên PQ, dãy Lucas thứ nhất Un(P,Q) và thứ hai Vn(P,Q) được xác định bằng hệ thức truy hồi :

Dễ thấy với thì

Hệ thức trên có thể biểu diễn dưới dạng ma trận như sau:

Ví dụ[sửa | sửa mã nguồn]

Các phần tử ban đầu của dãy Lucas Un(P,Q) và Vn(P,Q) được cho trong bảng:

Biểu thức tường minh[sửa | sửa mã nguồn]

Phương trình đặc trưng của hệ thức truy hồi cho dãy Lucas là:

Biệt thức delta với:

thì:

Lưu ý rằng dãy và dãy cũng thỏa mãn hệ thức truy hồi nhưng không phải dãy số nguyên.

Nghiệm phân biệt[sửa | sửa mã nguồn]

Khi , ab khác nhau thì có thể xác định:

Theo đó, dãy Lucas có thể được biểu diễn qua ab như sau

Nghiệm trùng nhau[sửa | sửa mã nguồn]

Trường hợp khi và chỉ khi với là số nguyên. Khi đó

.

Tính chất[sửa | sửa mã nguồn]

Hàm sinh[sửa | sửa mã nguồn]

Hàm sinh thông thường là

Phương trình Pell[sửa | sửa mã nguồn]

Khi , các dãy Lucas sẽ thỏa mãn phương trình Pell:

Quan hệ các dãy với tham số khác nhau[sửa | sửa mã nguồn]

  • Với c là số bất kỳ, các dãy với
có biệt thức như  :
  • Với c bất kỳ cũng có

Quan hệ khác[sửa | sửa mã nguồn]

Các phần tử của dãy Lucas thỏa mãn quan hệ tổng quát giữa dãy Fibonacci số Lucas . Ví dụ:

Tính chia hết[sửa | sửa mã nguồn]

là bội số của , như vậydãy chia hết. Cụ thể chỉ có thể là số nguyên tố khi n là số nguyên tố. Hệ quả khác là thuật toán bình phương và nhân để tính nhanh khi n có giá trị lớn. Hơn nữa, nếu thì là dãy số chia hết mạnh.

Các tính chia hết khác:[1]

  • Nếu n / m lẻ thì chia hết cho .
  • Gọi N là một số nguyên tố nhỏ hơn 2Q. Nếu tồn tại số nguyên dương r nhỏ nhất để N chia hết cho , thì đó tập hợp n thỏa mãn N chia hết cho chính là tập hợp các bội số của r.
  • Nếu PQ chẵn thì luôn chẵn, ngoại trừ
  • Nếu P chẵn và Q lẻ thì cùng tính chẵn lẻ với n luôn chẵn.
  • Nếu P lẻ và Q chẵn thì luôn lẻ với .
  • Nếu PQ đều lẻ thì chẵn khi và chỉ khi n là bội của 3.
  • Nếu p là một số nguyên tố lẻ thì (xem ký hiệu Legendre ).
  • Nếu p là số nguyên tố lẻ và chia PQ thì p chia hết Cho mọi .
  • Nếu p là số nguyên tố lẻ và chia P mà không chia cho Q thì p chia nếu và chỉ khi n chẵn.
  • Nếu p là một số nguyên tố lẻ và không chia P mà chia cho Q thì p không bao giờ chia .
  • Nếu p là số nguyên tố lẻ và không chia PQ mà chia D, thì p chia nếu và chỉ khi p chia cho n .
  • Nếu p là số nguyên tố lẻ và không chia PQD thì p chia hết , với .

Mệnh đề cuối cùng khái quát Định lý nhỏ Fermat. Những tính chất này được dùng trong Kiểm tra tính nguyên tố Lucas-Lehmer. Mệnh đề đảo của mệnh đề cuối không đúng, vì đình lý đảo của định lý nhỏ Fermat cũng không đúng. Tồn tại hợp số n nguyên tố cùng nhau với D và chia hết , với . Hợp số này được gọi là số giả nguyên tố Lucas.

Thừa số nguyên tố của một phần tử trong dãy Lucas mà không chia hết bất kỳ phần tử nào trước đó trong dãy được gọi là primitive. Định lý Carmichael phát biểu rằng tất cả ngoại trừ rất nhiều số hạng trong dãy Lucas đều có thừa số nguyên tố.[2] Thật vậy, Carmichael (1913) đã chỉ ra rằng nếu D dương và n khác 1, 2 hoặc 6 thì có một thừa số nguyên tố primitive. Trong trường hợp D âm, Bilu, Hanrot, Voutier và Mignotte[3] cho kết quả rằng nếu n > 30, thì có một thừa số nguyên tố primitive và xác định tất cả các trường hợp không có thừa số nguyên tố primitive.

Một số trường hợp cụ thể[sửa | sửa mã nguồn]

Dãy Lucas cho một số giá trị cụ thể của PQ:

Un(1,−1) : Dãy Fibonacci
Vn(1,−1) : Số Lucas
Un(2,−1) : Số Pell
Vn(2,−1) : Số Pell–Lucas
Un(1,−2) : Số Jacobsthal
Vn(1,−2) : Số Jacobsthal–Lucas
Un(3, 2) : Số nguyên tố Mersenne 2n − 1
Vn(3, 2) : Những số có dạng 2n + 1 bao gồm cả số Fermat[2]
Un(6, 1) : Căn bậc hai của số chính phương tam giác.
Un(x,−1) : Đa thức Fibonacci
Vn(x,−1) : Đa thức Lucas
Un(2x, 1) : Đa thức Chebyshev loại hai
Vn(2x, 1) : Đa thức Chebyshev loại một nhân 2
Un(x+1, x) : Chữ số lặp lại hệ cơ số x
Vn(x+1, x) : xn + 1

Một số dãy Lucas được ghi nhận trong Bảng tra cứu dãy số nguyên trực tuyến:

−1 3 OEISicon light.svgA214733
1 −1 OEISicon light.svgA000045 OEISicon light.svgA000032
1 1 OEISicon light.svgA128834 OEISicon light.svgA087204
1 2 OEISicon light.svgA107920 OEISicon light.svgA002249
2 −1 OEISicon light.svgA000129 OEISicon light.svgA002203
2 1 OEISicon light.svgA001477
2 2 OEISicon light.svgA009545 OEISicon light.svgA007395
2 3 OEISicon light.svgA088137
2 4 OEISicon light.svgA088138
2 5 OEISicon light.svgA045873
3 −5 OEISicon light.svgA015523 OEISicon light.svgA072263
3 −4 OEISicon light.svgA015521 OEISicon light.svgA201455
3 −3 OEISicon light.svgA030195 OEISicon light.svgA172012
3 −2 OEISicon light.svgA007482 OEISicon light.svgA206776
3 −1 OEISicon light.svgA006190 OEISicon light.svgA006497
3 1 OEISicon light.svgA001906 OEISicon light.svgA005248
3 2 OEISicon light.svgA000225 OEISicon light.svgA000051
3 5 OEISicon light.svgA190959
4 −3 OEISicon light.svgA015530 OEISicon light.svgA080042
4 −2 OEISicon light.svgA090017
4 −1 OEISicon light.svgA001076 OEISicon light.svgA014448
4 1 OEISicon light.svgA001353 OEISicon light.svgA003500
4 2 OEISicon light.svgA007070 OEISicon light.svgA056236
4 3 OEISicon light.svgA003462 OEISicon light.svgA034472
4 4 OEISicon light.svgA001787
5 −3 OEISicon light.svgA015536
5 −2 OEISicon light.svgA015535
5 −1 OEISicon light.svgA052918 OEISicon light.svgA087130
5 1 OEISicon light.svgA004254 OEISicon light.svgA003501
5 4 OEISicon light.svgA002450 OEISicon light.svgA052539
6 1 OEISicon light.svgA001109 OEISicon light.svgA003499

Ứng dụng[sửa | sửa mã nguồn]

  • Dãy Lucas được sử dụng trong kiểm tra xác suất giả nguyên tố Lucas nằm trong Kiểm tra tính nguyên tố Baillie-PSW thường dùng.
  • Dãy Lucas được dùng trong một số phương pháp chứng minh tính nguyên tố, bao gồm Kiểm tra Lucas-Lehmer-Riesel và các phương pháp khác trong Brillhart-Lehmer-Selfridge 1975[4]
  • LUC là hệ thống mật mã khóa công khai dựa trên dãy Lucas[5] thực hiện hệ analog ElGamal (LUCELG), Diffie – Hellman (LUCDIF) và RSA (LUCRSA). Việc mã hóa thông điệp trong LUC được tính như một phần tử của dãy Lucas nhất định, thay vì lũy thừa mô-đun như trong RSA hoặc Diffie – Hellman. Tuy nhiên, bài viết của Bleichenbacher và cộng sự[6] cho thấy nhiều lợi thế bảo mật của LUC là không chính xác hoặc không đáng kể khi so sánh với các hệ thống dựa trên lũy thừa mô đun.

Chú thích[sửa | sửa mã nguồn]

  1. ^ Xem tính liên hệ và chia hết này trong (Carmichael 1913), (Lehmer 1930) or (Ribenboim 1996).
  2. ^ a b Yabuta, M (2001). “A simple proof of Carmichael's theorem on primitive divisors” (PDF). Fibonacci Quarterly. 39: 439–443. Truy cập ngày 4 tháng 10 năm 2018.
  3. ^ Bilu, Yuri; Hanrot, Guillaume; Voutier, Paul M.; Mignotte, Maurice (2001). “Existence of primitive divisors of Lucas and Lehmer numbers” (PDF). J. Reine Angew. Math. 2001 (539): 75–122. doi:10.1515/crll.2001.080. MR 1863855.
  4. ^ John Brillhart; Derrick Henry Lehmer; John Selfridge (tháng 4 năm 1975). “New Primality Criteria and Factorizations of 2m ± 1”. Mathematics of Computation. 29: 620–647. doi:10.1090/S0025-5718-1975-0384673-1. JSTOR 2005583.
  5. ^ P. J. Smith; M. J. J. Lennon (1993). “LUC: A new public key system”. Proceedings of the Ninth IFIP Int. Symp. On Computer Security: 103–117. CiteSeerX 10.1.1.32.1835.
  6. ^ D. Bleichenbacher; W. Bosma; A. K. Lenstra (1995). “Some Remarks on Lucas-Based Cryptosystems” (PDF). Lecture Notes in Computer Science. 963: 386–396. doi:10.1007/3-540-44750-4_31. ISBN 978-3-540-60221-7.

 

Tham khảo[sửa | sửa mã nguồn]