✨Dãy Lucas

Trong toán học, dãy Lucas $U\_n(P,Q)$ và $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

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

với $P$ và $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 $U\_n(P,\; Q)$ và $V\_n(P,\; Q)$ .

Nói chung, dãy Lucas $U\_n(P,\; Q)$ và $V\_n(P,\; Q)$ biểu diễn dãy đa thức hệ số nguyên với biến $P$ và $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 :

: n(P,Q)&=P\cdot U{n-1}(P,Q)-Q\cdot U_{n-2}(P,Q) \mbox{ for }n>1, \end{align}

và

: $\backslash begin\{align\}$

V_0(P,Q)&=2, \ V_1(P,Q)&=P, \ Vn(P,Q)&=P\cdot V{n-1}(P,Q)-Q\cdot V_{n-2}(P,Q) \mbox{ for }n>1. \end{align}

Dễ thấy với $n>0$ thì

: $\backslash begin\{align\}\; U$n(P,Q)&=\frac{P\cdot U{n-1}(P,Q) + V_{n-1}(P,Q)}{2}, \ Vn(P,Q)&=\frac{(P^2-4Q)\cdot U{n-1}(P,Q)+P\cdot V_{n-1}(P,Q)}{2}. \end{align}

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

: $\backslash 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},

: $\backslash 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},

: $\backslash begin\{bmatrix\}\; U\_n(P,Q)\backslash \; 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:

:

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 $U\_n(P,Q)$ và $V\_n(P,Q)$ là:

: $x^2\; -\; Px\; +\; Q=0\; \backslash ,$

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

: $a\; =\; \backslash frac\{P+\backslash sqrt\{D2\backslash quad\backslash text\{và\}\backslash quad\; b\; =\; \backslash frac\{P-\backslash sqrt\{D2.\; \backslash ,$

thì:

: $a\; +\; b\; =\; P\backslash ,\; ,$ : $a\; b\; =\; \backslash frac\{1\}\{4\}(P^2\; -\; D)\; =\; Q\backslash ,\; ,$ : $a\; -\; b\; =\; \backslash sqrt\{D\}\backslash ,\; .$

Lưu ý rằng dãy $a^n$ và dãy $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 $D\backslash ne\; 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

: $U\_n=\; \backslash frac\{a^n-b^n\}\{a-b\}\; =\; \backslash frac\{a^n-b^n\}\{\; \backslash sqrt\{D$

: $V\_n=a^n+b^n\; \backslash ,$

Nghiệm trùng nhau

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

: $U\_n(P,Q)=U\_n(2S,S^2)\; =\; nS^\{n-1\}\backslash ,$

: $V\_n(P,Q)=V\_n(2S,S^2)=2S^n\backslash ,$ .

Tính chất

Hàm sinh

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

: $\backslash sum\_\{n\backslash ge\; 0\}\; U\_n(P,Q)z^n\; =\; \backslash frac\{z\}\{1-Pz+Qz^2\};$

: $\backslash sum\_\{n\backslash ge\; 0\}\; V\_n(P,Q)z^n\; =\; \backslash frac\{2-Pz\}\{1-Pz+Qz^2\}.$

Phương trình Pell

Khi $Q=\backslash pm\; 1$, các dãy Lucas $U\_n(P,\; Q)$ và $V\_n(P,\; Q)$ sẽ thỏa mãn phương trình Pell:

: $V\_n(P,1)^2\; -\; D\backslash cdot\; U$n(P,1)^2 = 4, : $V${2n}(P,-1)^2 - D\cdot U{2n}(P,-1)^2 = 4, : $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 $U\_n(P\text{'},\; Q\text{'})$ và $V\_n(P\text{'},\; Q\text{'})$ với

:: $P\text{'}\; =\; P\; +\; 2c$ :: $Q\text{'}\; =\; cP\; +\; Q\; +\; c^2$ : có biệt thức như $U\_n(P,\; Q)$ và $V\_n(P,\; Q)$ : :: $P\text{'}^2\; -\; 4Q\text{'}\; =\; (P+2c)^2\; -\; 4(cP\; +\; Q\; +\; c^2)\; =\; P^2\; -\; 4Q\; =\; D.$

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

:: $U\_n(cP,c^2Q)\; =\; c^\{n-1\}\backslash cdot\; U\_n(P,Q),$ :: $V\_n(cP,c^2Q)\; =\; c^n\backslash 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 $F\_n=U\_n(1,-1)$ và số Lucas $L\_n=V\_n(1,-1)$. Ví dụ:

: n = {V{n+1} - Q V{n-1=2V{n+1}-P V_n & 5Fn = {L{n+1} + L{n-1=2L{n+1} - L_{n} \ Vn = U{n+1} - Q U{n-1}=2U{n+1}-PU_n & Ln = F{n+1} + F{n-1}=2F{n+1}-Fn \ U{2n} = U_n Vn & F{2n} = F_n Ln \ V{2n} = Vn^2 - 2Q^n & L{2n} = Ln^2 - 2(-1)^n \ U{m+n} = Un U{m+1} - Q Um U{n-1}=\frac{U_mV_n+U_nVm}{2} & F{m+n} = Fn F{m+1} + Fm F{n-1}=\frac{F_mL_n+F_nLm}{2} \ V{m+n} = V_m Vn - Q^n V{m-n} = D U_m Un + Q^n V{m-n} & L_{m+n} = L_m Ln - (-1)^n L{m-n} = 5 F_m Fn + (-1)^n L{m-n} \ V_n^2-DU_n^2=4Q^n & L_n^2-5F_n^2=4(-1)^n \ Un^2-U{n-1}U_{n+1}=Q^{n-1} & Fn^2-F{n-1}F_{n+1}=(-1)^{n-1} \ Vn^2-V{n-1}V_{n+1}=DQ^{n-1} & Ln^2-L{n-1}L_{n+1}=5(-1)^{n-1} \ DUn=V{n+1}-QV_{n-1} & Fn=\frac{L{n+1}+L{n-1{5} \ V{m+n}=\frac{V_mV_n+DU_mUn}{2} & L{m+n}=\frac{L_mL_n+5F_mFn}{2} \ U{m+n}=U_mVn-Q^nU{m-n} & F_{n+m}=F_mLn-(-1)^nF{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

$U\_\{km\}(P,Q)$ là bội số của $U\_m(P,Q)$, như vậy$(U\_m(P,Q))\_\{m\backslash ge1\}$ là dãy chia hết. Cụ thể $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 $U\_n(P,Q)$ khi _n_ có giá trị lớn. Hơn nữa, nếu $\backslash gcd(P,Q)=1$ thì $(U\_m(P,Q))\_\{m\backslash ge1\}$ là dãy số chia hết mạnh.

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

• Nếu n / m lẻ thì $V\_m$ chia hết cho $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 $U\_r$, thì đó tập hợp n thỏa mãn N chia hết cho $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ì $U\_n,\; V\_n$ luôn chẵn, ngoại trừ $U\_1$
• Nếu P chẵn và Q lẻ thì $U\_n$ cùng tính chẵn lẻ với n và $V\_n$ luôn chẵn.
• Nếu P lẻ và Q chẵn thì $U\_n,\; V\_n$ luôn lẻ với $n=1,\; 2,\; \backslash ldots$ .
• Nếu P và Q đều lẻ thì $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ì $U\_p\backslash equiv\backslash left(\backslash tfrac\{D\}\{p\}\backslash right),\; V\_p\backslash equiv\; P\backslash 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 $U\_n$ Cho mọi $n>1$ .
• Nếu p là số nguyên tố lẻ và chia P mà không chia cho Q thì p chia $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 $U\_n$ vì $n=1,\; 2,\; \backslash ldots$ .
• Nếu p là số nguyên tố lẻ và không chia PQ mà chia D, thì p chia $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 $U\_l$, với $l=p-\backslash left(\backslash tfrac\{D\}\{p\}\backslash 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 $U\_l$, với $l=n-\backslash left(\backslash tfrac\{D\}\{n\}\backslash 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ố. 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ì $U\_n$ 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ì $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 $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:

: : Dãy Fibonacci : : Số Lucas : : Số Pell : : Số Pell–Lucas : : Số Jacobsthal : : Số Jacobsthal–Lucas : : Số nguyên tố Mersenne 2ⁿ − 1 : : Những số có dạng 2ⁿ + 1 bao gồm cả số Fermat

• 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.