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 :

: \begin{align}
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{align}

và

: \begin{align}

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{align}

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

: \begin{align}
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{align}

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

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

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

: \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:

:
\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 U_n(P,Q) và V_n(P,Q) là:

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

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

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

thì:

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

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\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= \frac{a^n-b^n}{a-b} = \frac{a^n-b^n}{ \sqrt{D}}

: V_n=a^n+b^n \,

Nghiệm trùng nhau
Trường hợp D=0 khi và chỉ khi P=2S \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}\,

: 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à

:
\sum_{n\ge 0} U_n(P,Q)z^n = \frac{z}{1-Pz+Qz^2};

:
\sum_{n\ge 0} V_n(P,Q)z^n = \frac{2-Pz}{1-Pz+Qz^2}.

Phương trình Pell
Khi Q=\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\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', Q') và V_n(P', Q') với

:: P' = P + 2c
:: Q' = cP + Q + c^2
: có biệt thức như U_n(P, Q) và V_n(P, Q) :
:: P'^2 - 4Q' = (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}\cdot U_n(P,Q),
:: V_n(cP,c^2Q) = 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 F_n=U_n(1,-1) và số Lucas L_n=V_n(1,-1). Ví dụ:

:
\begin{array}{r|l}
\text{Trường hợp chung} & (P,Q) = (1,-1)
\\
\hline
(P^2-4Q) U_n = {V_{n+1} - Q V_{n-1}}=2V_{n+1}-P V_n & 5F_n = {L_{n+1} + L_{n-1}}=2L_{n+1} - L_{n}
\\
V_n = U_{n+1} - Q U_{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} - Q U_m U_{n-1}=\frac{U_mV_n+U_nV_m}{2} & F_{m+n} = F_n F_{m+1} + F_m F_{n-1}=\frac{F_mL_n+F_nL_m}{2}
\\
V_{m+n} = V_m V_n - Q^n V_{m-n} = D U_m U_n + Q^n V_{m-n} & L_{m+n} = L_m L_n - (-1)^n L_{m-n} = 5 F_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_mV_n+DU_mU_n}{2} & L_{m+n}=\frac{L_mL_n+5F_mF_n}{2}
\\
U_{m+n}=U_mV_n-Q^nU_{m-n} & F_{n+m}=F_mL_n-(-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\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 \gcd(P,Q)=1 thì (U_m(P,Q))_{m\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, \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\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 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, \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-\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 U_l, với 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ố. 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 &x3E; 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 2n&nbsp;&x2212;&nbsp;1
: : Những số có dạng 2n&nbsp;+&nbsp;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.

Chú thích


Tham khảo













Dãy Lucas tại Bách khoa toàn thư Toán học