Dãy Lucas

Trong toán học, dãy Lucas ${\displaystyle U_{n}(P,Q)}$ và ${\displaystyle V_{n}(P,Q)}$ là các dãy số nguyên đệ quy không đổi thỏa mãn hệ thức truy hồi

${\displaystyle x_{n}=P\cdot x_{n-1}-Q\cdot x_{n-2}}$

với ${\displaystyle P}$ và ${\displaystyle Q}$ 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 ${\displaystyle U_{n}(P,Q)}$ và ${\displaystyle V_{n}(P,Q)}$ .

Nói chung, dãy Lucas ${\displaystyle U_{n}(P,Q)}$ và ${\displaystyle V_{n}(P,Q)}$ biểu diễn dãy đa thức hệ số nguyên với biến ${\displaystyle P}$ và ${\displaystyle Q}$.

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_n(P,Q) và thứ hai V_n(P,Q) được xác định bằng hệ thức truy hồi :

${\displaystyle {\begin{aligned}U_{0}(P,Q)&=0,\\U_{1}(P,Q)&=1,\\U_{n}(P,Q)&=P\cdot U_{n-1}(P,Q)-Q\cdot U_{n-2}(P,Q){\mbox{ for }}n>1,\end{aligned}}}$

và

${\displaystyle {\begin{aligned}V_{0}(P,Q)&=2,\\V_{1}(P,Q)&=P,\\V_{n}(P,Q)&=P\cdot V_{n-1}(P,Q)-Q\cdot V_{n-2}(P,Q){\mbox{ for }}n>1.\end{aligned}}}$

Dễ thấy với ${\displaystyle n>0}$ thì

${\displaystyle {\begin{aligned}U_{n}(P,Q)&={\frac {P\cdot U_{n-1}(P,Q)+V_{n-1}(P,Q)}{2}},\\V_{n}(P,Q)&={\frac {(P^{2}-4Q)\cdot U_{n-1}(P,Q)+P\cdot V_{n-1}(P,Q)}{2}}.\end{aligned}}}$

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

${\displaystyle {\begin{bmatrix}U_{n}(P,Q)\\U_{n+1}(P,Q)\end{bmatrix}}={\begin{bmatrix}0&1\\-Q&P\end{bmatrix}}\cdot {\begin{bmatrix}U_{n-1}(P,Q)\\U_{n}(P,Q)\end{bmatrix}},}$

${\displaystyle {\begin{bmatrix}V_{n}(P,Q)\\V_{n+1}(P,Q)\end{bmatrix}}={\begin{bmatrix}0&1\\-Q&P\end{bmatrix}}\cdot {\begin{bmatrix}V_{n-1}(P,Q)\\V_{n}(P,Q)\end{bmatrix}},}$

${\displaystyle {\begin{bmatrix}U_{n}(P,Q)\\V_{n}(P,Q)\end{bmatrix}}={\begin{bmatrix}P/2&1/2\\(P^{2}-4Q)/2&P/2\end{bmatrix}}\cdot {\begin{bmatrix}U_{n-1}(P,Q)\\V_{n-1}(P,Q)\end{bmatrix}}.}$

Ví dụ

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

${\displaystyle {\begin{array}{r|l|l}n&U_{n}(P,Q)&V_{n}(P,Q)\\\hline 0&0&2\\1&1&P\\2&P&{P}^{2}-2Q\\3&{P}^{2}-Q&{P}^{3}-3PQ\\4&{P}^{3}-2PQ&{P}^{4}-4{P}^{2}Q+2{Q}^{2}\\5&{P}^{4}-3{P}^{2}Q+{Q}^{2}&{P}^{5}-5{P}^{3}Q+5P{Q}^{2}\\6&{P}^{5}-4{P}^{3}Q+3P{Q}^{2}&{P}^{6}-6{P}^{4}Q+9{P}^{2}{Q}^{2}-2{Q}^{3}\end{array}}}$

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 ${\displaystyle U_{n}(P,Q)}$ và ${\displaystyle V_{n}(P,Q)}$ là:

${\displaystyle x^{2}-Px+Q=0\,}$

Biệt thức delta ${\displaystyle D=P^{2}-4Q}$ với:

${\displaystyle a={\frac {P+{\sqrt {D}}}{2}}\quad {\text{và}}\quad b={\frac {P-{\sqrt {D}}}{2}}.\,}$

thì:

${\displaystyle a+b=P\,,}$

${\displaystyle ab={\frac {1}{4}}(P^{2}-D)=Q\,,}$

${\displaystyle a-b={\sqrt {D}}\,.}$

Lưu ý rằng dãy ${\displaystyle a^{n}}$ và dãy ${\displaystyle b^{n}}$ 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 ${\displaystyle D\neq 0}$, 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

${\displaystyle U_{n}={\frac {a^{n}-b^{n}}{a-b}}={\frac {a^{n}-b^{n}}{\sqrt {D}}}}$

${\displaystyle V_{n}=a^{n}+b^{n}\,}$

Nghiệm trùng nhau

Trường hợp ${\displaystyle D=0}$ khi và chỉ khi ${\displaystyle P=2S{\text{ và }}Q=S^{2}}$ với ${\displaystyle a=b=S}$ là số nguyên. Khi đó

${\displaystyle U_{n}(P,Q)=U_{n}(2S,S^{2})=nS^{n-1}\,}$

${\displaystyle V_{n}(P,Q)=V_{n}(2S,S^{2})=2S^{n}\,}$ .

Tính chất

Hàm sinh

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

${\displaystyle \sum _{n\geq 0}U_{n}(P,Q)z^{n}={\frac {z}{1-Pz+Qz^{2}}};}$

${\displaystyle \sum _{n\geq 0}V_{n}(P,Q)z^{n}={\frac {2-Pz}{1-Pz+Qz^{2}}}.}$

Phương trình Pell

Khi ${\displaystyle Q=\pm 1}$, các dãy Lucas ${\displaystyle U_{n}(P,Q)}$ và ${\displaystyle V_{n}(P,Q)}$ sẽ thỏa mãn phương trình Pell:

${\displaystyle V_{n}(P,1)^{2}-D\cdot U_{n}(P,1)^{2}=4,}$

${\displaystyle V_{2n}(P,-1)^{2}-D\cdot U_{2n}(P,-1)^{2}=4,}$

${\displaystyle V_{2n+1}(P,-1)^{2}-D\cdot U_{2n+1}(P,-1)^{2}=-4.}$

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 ${\displaystyle U_{n}(P',Q')}$ và ${\displaystyle V_{n}(P',Q')}$ với

${\displaystyle P'=P+2c}$

${\displaystyle Q'=cP+Q+c^{2}}$

có biệt thức như ${\displaystyle U_{n}(P,Q)}$ và ${\displaystyle V_{n}(P,Q)}$ :

${\displaystyle P'^{2}-4Q'=(P+2c)^{2}-4(cP+Q+c^{2})=P^{2}-4Q=D.}$

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

${\displaystyle U_{n}(cP,c^{2}Q)=c^{n-1}\cdot U_{n}(P,Q),}$

${\displaystyle V_{n}(cP,c^{2}Q)=c^{n}\cdot V_{n}(P,Q).}$

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 ${\displaystyle F_{n}=U_{n}(1,-1)}$ và số Lucas ${\displaystyle L_{n}=V_{n}(1,-1)}$. Ví dụ:

${\displaystyle {\begin{array}{r|l}{\text{Trường hợp chung}}&(P,Q)=(1,-1)\\\hline (P^{2}-4Q)U_{n}={V_{n+1}-QV_{n-1}}=2V_{n+1}-PV_{n}&5F_{n}={L_{n+1}+L_{n-1}}=2L_{n+1}-L_{n}\\V_{n}=U_{n+1}-QU_{n-1}=2U_{n+1}-PU_{n}&L_{n}=F_{n+1}+F_{n-1}=2F_{n+1}-F_{n}\\U_{2n}=U_{n}V_{n}&F_{2n}=F_{n}L_{n}\\V_{2n}=V_{n}^{2}-2Q^{n}&L_{2n}=L_{n}^{2}-2(-1)^{n}\\U_{m+n}=U_{n}U_{m+1}-QU_{m}U_{n-1}={\frac {U_{m}V_{n}+U_{n}V_{m}}{2}}&F_{m+n}=F_{n}F_{m+1}+F_{m}F_{n-1}={\frac {F_{m}L_{n}+F_{n}L_{m}}{2}}\\V_{m+n}=V_{m}V_{n}-Q^{n}V_{m-n}=DU_{m}U_{n}+Q^{n}V_{m-n}&L_{m+n}=L_{m}L_{n}-(-1)^{n}L_{m-n}=5F_{m}F_{n}+(-1)^{n}L_{m-n}\\V_{n}^{2}-DU_{n}^{2}=4Q^{n}&L_{n}^{2}-5F_{n}^{2}=4(-1)^{n}\\U_{n}^{2}-U_{n-1}U_{n+1}=Q^{n-1}&F_{n}^{2}-F_{n-1}F_{n+1}=(-1)^{n-1}\\V_{n}^{2}-V_{n-1}V_{n+1}=DQ^{n-1}&L_{n}^{2}-L_{n-1}L_{n+1}=5(-1)^{n-1}\\DU_{n}=V_{n+1}-QV_{n-1}&F_{n}={\frac {L_{n+1}+L_{n-1}}{5}}\\V_{m+n}={\frac {V_{m}V_{n}+DU_{m}U_{n}}{2}}&L_{m+n}={\frac {L_{m}L_{n}+5F_{m}F_{n}}{2}}\\U_{m+n}=U_{m}V_{n}-Q^{n}U_{m-n}&F_{n+m}=F_{m}L_{n}-(-1)^{n}F_{m-n}\\2^{n-1}U_{n}={n \choose 1}P^{n-1}+{n \choose 3}P^{n-3}D+\cdots &2^{n-1}F_{n}={n \choose 1}+5{n \choose 3}+\cdots \\2^{n-1}V_{n}=P^{n}+{n \choose 2}P^{n-2}D+{n \choose 4}P^{n-4}D^{2}+\cdots &2^{n-1}L_{n}=1+5{n \choose 2}+5^{2}{n \choose 4}+\cdots \end{array}}}$

Tính chia hết

${\displaystyle U_{km}(P,Q)}$ là bội số của ${\displaystyle U_{m}(P,Q)}$, như vậy${\displaystyle (U_{m}(P,Q))_{m\geq 1}}$ là dãy chia hết. Cụ thể ${\displaystyle U_{n}(P,Q)}$ 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 ${\displaystyle U_{n}(P,Q)}$ khi n có giá trị lớn. Hơn nữa, nếu ${\displaystyle \gcd(P,Q)=1}$ thì ${\displaystyle (U_{m}(P,Q))_{m\geq 1}}$ 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ì ${\displaystyle V_{m}}$ chia hết cho ${\displaystyle V_{n}}$ .
• 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 ${\displaystyle U_{r}}$, thì đó tập hợp n thỏa mãn N chia hết cho ${\displaystyle U_{n}}$ chính là tập hợp các bội số của r.
• Nếu P và Q chẵn thì ${\displaystyle U_{n},V_{n}}$ luôn chẵn, ngoại trừ ${\displaystyle U_{1}}$
• Nếu P chẵn và Q lẻ thì ${\displaystyle U_{n}}$ cùng tính chẵn lẻ với n và ${\displaystyle V_{n}}$ luôn chẵn.
• Nếu P lẻ và Q chẵn thì ${\displaystyle U_{n},V_{n}}$ luôn lẻ với ${\displaystyle n=1,2,\ldots }$ .
• Nếu P và Q đều lẻ thì ${\displaystyle U_{n},V_{n}}$ 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ì ${\displaystyle U_{p}\equiv \left({\tfrac {D}{p}}\right),V_{p}\equiv P{\pmod {p}}}$ (xem ký hiệu Legendre ).
• Nếu p là số nguyên tố lẻ và chia P và Q thì p chia hết ${\displaystyle U_{n}}$ Cho mọi ${\displaystyle n>1}$ .
• Nếu p là số nguyên tố lẻ và chia P mà không chia cho Q thì p chia ${\displaystyle U_{n}}$ 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 ${\displaystyle U_{n}}$ vì ${\displaystyle n=1,2,\ldots }$ .
• Nếu p là số nguyên tố lẻ và không chia PQ mà chia D, thì p chia ${\displaystyle U_{n}}$ 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 ${\displaystyle U_{l}}$, với ${\displaystyle l=p-\left({\tfrac {D}{p}}\right)}$ .

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 ${\displaystyle U_{l}}$, với ${\displaystyle l=n-\left({\tfrac {D}{n}}\right)}$. 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ì ${\displaystyle U_{n}}$ 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ì ${\displaystyle U_{n}}$ có một thừa số nguyên tố primitive và xác định tất cả các trường hợp ${\displaystyle U_{n}}$ 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:

U_n(1,−1) : Dãy Fibonacci

V_n(1,−1) : Số Lucas

U_n(2,−1) : Số Pell

V_n(2,−1) : Số Pell–Lucas

U_n(1,−2) : Số Jacobsthal

V_n(1,−2) : Số Jacobsthal–Lucas

U_n(3, 2) : Số nguyên tố Mersenne 2ⁿ − 1

V_n(3, 2) : Những số có dạng 2ⁿ + 1 bao gồm cả số Fermat^[2]

U_n(6, 1) : Căn bậc hai của số chính phương tam giác.

U_n(x,−1) : Đa thức Fibonacci

V_n(x,−1) : Đa thức Lucas

U_n(2x, 1) : Đa thức Chebyshev loại hai

V_n(2x, 1) : Đa thức Chebyshev loại một nhân 2

U_n(x+1, x) : Chữ số lặp lại hệ cơ số x

V_n(x+1, x) : xⁿ + 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:

${\displaystyle P\,}$	${\displaystyle Q\,}$	${\displaystyle U_{n}(P,Q)\,}$	${\displaystyle V_{n}(P,Q)\,}$
−1	3	A214733
1	−1	A000045	A000032
1	1	A128834	A087204
1	2	A107920	A002249
2	−1	A000129	A002203
2	1	A001477
2	2	A009545	A007395
2	3	A088137
2	4	A088138
2	5	A045873
3	−5	A015523	A072263
3	−4	A015521	A201455
3	−3	A030195	A172012
3	−2	A007482	A206776
3	−1	A006190	A006497
3	1	A001906	A005248
3	2	A000225	A000051
3	5	A190959
4	−3	A015530	A080042
4	−2	A090017
4	−1	A001076	A014448
4	1	A001353	A003500
4	2	A007070	A056236
4	3	A003462	A034472
4	4	A001787
5	−3	A015536
5	−2	A015535
5	−1	A052918	A087130
5	1	A004254	A003501
5	4	A002450	A052539
6	1	A001109	A003499

Ứ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^[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

 

Tham khảo

• Carmichael, R. D. (1913), “On the numerical factors of the arithmetic forms αⁿ±βⁿ”, Annals of Mathematics, 15 (1/4), tr. 30–70, doi:10.2307/1967797, JSTOR 1967797
• Lehmer, D. H. (1930). “An extended theory of Lucas' functions”. Annals of Mathematics. 31: 419–448. Bibcode:1930AnMat..31..419L. doi:10.2307/1968235. JSTOR 1968235.
• Ward, Morgan (1954). “Prime divisors of second order recurring sequences”. Duke Math. J. 21: 607–614. doi:10.1215/S0012-7094-54-02163-8. MR 0064073.
• Somer, Lawrence (1980). “The divisibility properties of primary Lucas Recurrences with respect to primes” (PDF). Fibonacci Quarterly. 18: 316.
• Lagarias, J. C. (1985). “The set of primes dividing Lucas Numbers has density 2/3”. Pac. J. Math. 118: 449–461. doi:10.2140/pjm.1985.118.449. MR 0789184.
• Hans Riesel (1994). Prime Numbers and Computer Methods for Factorization. Progress in Mathematics. 126 (ấn bản 2). Birkhäuser. tr. 107–121. ISBN 0-8176-3743-5.
• Ribenboim, Paulo; McDaniel, Wayne L. (1996). “The square terms in Lucas Sequences”. J. Number Theory. 58: 104–123. doi:10.1006/jnth.1996.0068.
• Joye, M.; Quisquater, J.-J. (1996). “Efficient computation of full Lucas sequences” (PDF). Electronics Letters. 32: 537–538. doi:10.1049/el:19960359. Bản gốc (PDF) lưu trữ ngày 2 tháng 2 năm 2015.
• Ribenboim, Paulo (1996). The New Book of Prime Number Records . Springer-Verlag, New York. doi:10.1007/978-1-4612-0759-7. ISBN 978-1-4612-0759-7.
• Ribenboim, Paulo (2000). My Numbers, My Friends: Popular Lectures on Number Theory. New York: Springer-Verlag. tr. 1–50. ISBN 0-387-98911-0.
• Luca, Florian (2000). “Perfect Fibonacci and Lucas numbers”. Rend. Circ Matem. Palermo. 49: 313–318. doi:10.1007/BF02904236.
• Yabuta, M. (2001). “A simple proof of Carmichael's theorem on primitive divisors” (PDF). Fibonacci Quarterly. 39: 439–443.
• Benjamin, Arthur T.; Quinn, Jennifer J. (2003). Proofs that Really Count: The Art of Combinatorial Proof. Dolciani Mathematical Expositions. 27. Mathematical Association of America. tr. 35. ISBN 978-0-88385-333-7.
• Dãy Lucas tại Bách khoa toàn thư Toán học (tiếng Anh)
• Weisstein, Eric W., "Lucas Sequence" từ MathWorld.
• Wei Dai. “Lucas Sequences in Cryptography”.