Dãy Lucas

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

với formula_4 và formula_5 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 formula_6 và formula_2 .

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

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 ==
Cho hai tham số nguyên "P" và "Q", dãy Lucas thứ nhất "U"("P","Q") và thứ hai "V"("P","Q") được xác định bằng hệ thức truy hồi :

và

Dễ thấy với formula_14 thì

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

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

== Biểu thức tường minh ==
Phương trình đặc trưng của hệ thức truy hồi cho dãy Lucas formula_1 và formula_21 là:

Biệt thức delta formula_23 với:

thì:

Lưu ý rằng dãy formula_28 và dãy formula_29 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 ===
Khi formula_30, "a" và "b" khác nhau thì có thể xác định:

Theo đó, dãy Lucas có thể được biểu diễn qua "a" và "b" như sau

=== Nghiệm trùng nhau ===
Trường hợp formula_33 khi và chỉ khi formula_34 với formula_35 là số nguyên. Khi đó

== Tính chất ==
=== Hàm sinh ===
Hàm sinh thông thường là

=== Phương trình Pell ===
Khi formula_40, các dãy Lucas formula_6 và formula_2 sẽ thỏa mãn phương trình Pell:

=== Quan hệ các dãy với tham số khác nhau ===
- Với "c" là số bất kỳ, các dãy formula_46 và formula_47 với

- Với "c" bất kỳ cũng có

=== Quan hệ khác ===
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 formula_55 và số Lucas formula_56. Ví dụ:

=== Tính chia hết ===
formula_58 là bội số của formula_59, như vậyformula_60 là dãy chia hết. Cụ thể formula_1 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 formula_1 khi "n" có giá trị lớn. Hơn nữa, nếu formula_63 thì formula_60 là dãy số chia hết mạnh.

Các tính chia hết khác:

- Nếu "n" / "m" lẻ thì formula_65 chia hết cho formula_66 .
- Gọi "N" là một số nguyên tố nhỏ hơn 2"Q." Nếu tồn tại số nguyên dương "r" nhỏ nhất để "N" chia hết cho formula_67, thì đó tập hợp "n" thỏa mãn "N" chia hết cho formula_68 chính là tập hợp các bội số của "r".
- Nếu "P" và "Q" chẵn thì formula_69 luôn chẵn, ngoại trừ formula_70
- Nếu "P" chẵn và "Q" lẻ thì formula_68 cùng tính chẵn lẻ với "n" và formula_66 luôn chẵn.
- Nếu "P" lẻ và "Q" chẵn thì formula_69 luôn lẻ với formula_74 .
- Nếu "P" và "Q" đều lẻ thì formula_69 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ì formula_76 (xem ký hiệu Legendre ).
- Nếu "p" là số nguyên tố lẻ và chia "P" và "Q" thì "p" chia hết formula_68 Cho mọi formula_78 .
- Nếu "p" là số nguyên tố lẻ và chia "P" mà không chia cho "Q" thì "p" chia formula_68 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 formula_68 vì formula_74 .
- Nếu "p" là số nguyên tố lẻ và không chia "PQ" mà chia "D", thì "p" chia formula_68 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 formula_83, với formula_84 .

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 formula_83, với formula_86. 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ố. 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ì formula_68 có một thừa số nguyên tố primitive. Trong trường hợp "D" âm, Bilu, Hanrot, Voutier và Mignotte cho kết quả rằng nếu "n" > 30, thì formula_68 có một thừa số nguyên tố primitive và xác định tất cả các trường hợp formula_68 không có thừa số nguyên tố primitive.

== Một số trường hợp cụ thể ==
Dãy Lucas cho một số giá trị cụ thể của "P" và "Q":

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:

== Ứng dụng ==
- 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
- LUC là hệ thống mật mã khóa công khai dựa trên dãy Lucas 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ự 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.

== Tham khảo ==
- "Dãy Lucas" tại Bách khoa toàn thư Toán học
- </templatestyles>