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{matrix} 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) for n > 1, \end{matrix}

và

\begin{matrix} 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) for n > 1 . \end{matrix}

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

\begin{matrix} 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} - 4 Q) \cdot U_{n - 1} (P, Q) + P \cdot V_{n - 1} (P, Q)}{2} . \end{matrix}

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

[\begin{matrix} U_{n} (P, Q) \\ U_{n + 1} (P, Q) \end{matrix}] = [\begin{matrix} 0 & 1 \\ - Q & P \end{matrix}] \cdot [\begin{matrix} U_{n - 1} (P, Q) \\ U_{n} (P, Q) \end{matrix}],

[\begin{matrix} V_{n} (P, Q) \\ V_{n + 1} (P, Q) \end{matrix}] = [\begin{matrix} 0 & 1 \\ - Q & P \end{matrix}] \cdot [\begin{matrix} V_{n - 1} (P, Q) \\ V_{n} (P, Q) \end{matrix}],

[\begin{matrix} U_{n} (P, Q) \\ V_{n} (P, Q) \end{matrix}] = [\begin{matrix} P / 2 & 1 / 2 \\ (P^{2} - 4 Q) / 2 & P / 2 \end{matrix}] \cdot [\begin{matrix} U_{n - 1} (P, Q) \\ V_{n - 1} (P, Q) \end{matrix}] .

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{matrix} n & U_{n} (P, Q) & V_{n} (P, Q) \\ 0 & 0 & 2 \\ 1 & 1 & P \\ 2 & P & P^{2} - 2 Q \\ 3 & P^{2} - Q & P^{3} - 3 P Q \\ 4 & P^{3} - 2 P Q & P^{4} - 4 P^{2} Q + 2 Q^{2} \\ 5 & P^{4} - 3 P^{2} Q + Q^{2} & P^{5} - 5 P^{3} Q + 5 P Q^{2} \\ 6 & P^{5} - 4 P^{3} Q + 3 P Q^{2} & P^{6} - 6 P^{4} Q + 9 P^{2} Q^{2} - 2 Q^{3} \end{matrix}

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} - P x + Q = 0

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

a = \frac{P + \sqrt{D}}{2} và 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 \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

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 = 2 S và Q = S^{2}$ với $a = b = S$ là số nguyên. Khi đó

U_{n} (P, Q) = U_{n} (2 S, S^{2}) = n S^{n - 1}

V_{n} (P, Q) = V_{n} (2 S, S^{2}) = 2 S^{n}

.

Tính chất

Hàm sinh

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

\sum_{n \geq 0} U_{n} (P, Q) z^{n} = \frac{z}{1 - P z + Q z^{2}};

\sum_{n \geq 0} V_{n} (P, Q) z^{n} = \frac{2 - P z}{1 - P z + Q z^{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_{2 n} (P, - 1)^{2} - D \cdot U_{2 n} (P, - 1)^{2} = 4,

V_{2 n + 1} (P, - 1)^{2} - D \cdot U_{2 n + 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 + 2 c

Q^{'} = c P + Q + c^{2}

có biệt thức như

U_{n} (P, Q)

và

V_{n} (P, Q)

:

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

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

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

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

\begin{matrix} Trường hợp chung & (P, Q) = (1, - 1) \\ (P^{2} - 4 Q) U_{n} = V_{n + 1} - Q V_{n - 1} = 2 V_{n + 1} - P V_{n} & 5 F_{n} = L_{n + 1} + L_{n - 1} = 2 L_{n + 1} - L_{n} \\ V_{n} = U_{n + 1} - Q U_{n - 1} = 2 U_{n + 1} - P U_{n} & L_{n} = F_{n + 1} + F_{n - 1} = 2 F_{n + 1} - F_{n} \\ U_{2 n} = U_{n} V_{n} & F_{2 n} = F_{n} L_{n} \\ V_{2 n} = V_{n}^{2} - 2 Q^{n} & L_{2 n} = L_{n}^{2} - 2 (- 1)^{n} \\ U_{m + n} = U_{n} U_{m + 1} - Q U_{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} = 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} - D U_{n}^{2} = 4 Q^{n} & L_{n}^{2} - 5 F_{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} = D Q^{n - 1} & L_{n}^{2} - L_{n - 1} L_{n + 1} = 5 (- 1)^{n - 1} \\ D U_{n} = V_{n + 1} - Q V_{n - 1} & F_{n} = \frac{L_{n + 1} + L_{n - 1}}{5} \\ V_{m + n} = \frac{V_{m} V_{n} + D U_{m} U_{n}}{2} & L_{m + n} = \frac{L_{m} L_{n} + 5 F_{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} = (\binom{n}{1}) P^{n - 1} + (\binom{n}{3}) P^{n - 3} D + \dots & 2^{n - 1} F_{n} = (\binom{n}{1}) + 5 (\binom{n}{3}) + \dots \\ 2^{n - 1} V_{n} = P^{n} + (\binom{n}{2}) P^{n - 2} D + (\binom{n}{4}) P^{n - 4} D^{2} + \dots & 2^{n - 1} L_{n} = 1 + 5 (\binom{n}{2}) + 5^{2} (\binom{n}{4}) + \dots \end{matrix}

Tính chia hết

$U_{k m} (P, Q)$ là bội số của $U_{m} (P, Q)$ , như vậy $(U_{m} (P, Q))_{m \geq 1}$ 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 \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ì $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, \dots$ .
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 (\frac{D}{p}), V_{p} \equiv P (\mod 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, \dots$ .
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 - (\frac{D}{p})$ .

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 - (\frac{D}{n})$ . 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ì $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ì $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:

Bản mẫu:Math : Dãy Fibonacci

Bản mẫu:Math : Số Lucas

Bản mẫu:Math : Số Pell

Bản mẫu:Math : Số Pell–Lucas

Bản mẫu:Math : Số Jacobsthal

Bản mẫu:Math : Số Jacobsthal–Lucas

Bản mẫu:Math : Số nguyên tố Mersenne 2ⁿ − 1

Bản mẫu:Math : Những số có dạng 2ⁿ + 1 bao gồm cả số Fermat^[2]

Bản mẫu:Math : Căn bậc hai của số chính phương tam giác.

Bản mẫu:Math : Đa thức Fibonacci

Bản mẫu:Math : Đa thức Lucas

Bản mẫu:Math : Đa thức Chebyshev loại hai

Bản mẫu:Math : Đa thức Chebyshev loại một nhân 2

Bản mẫu:Math : Chữ số lặp lại hệ cơ số x

Bản mẫu:Math : 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:

$P$	$Q$	$U_{n} (P, Q)$	$V_{n} (P, Q)$
−1	3	Bản mẫu:OEIS2C
1	−1	Bản mẫu:OEIS2C	Bản mẫu:OEIS2C
1	1	Bản mẫu:OEIS2C	Bản mẫu:OEIS2C
1	2	Bản mẫu:OEIS2C	Bản mẫu:OEIS2C
2	−1	Bản mẫu:OEIS2C	Bản mẫu:OEIS2C
2	1	Bản mẫu:OEIS2C
2	2	Bản mẫu:OEIS2C	Bản mẫu:OEIS2C
2	3	Bản mẫu:OEIS2C
2	4	Bản mẫu:OEIS2C
2	5	Bản mẫu:OEIS2C
3	−5	Bản mẫu:OEIS2C	Bản mẫu:OEIS2C
3	−4	Bản mẫu:OEIS2C	Bản mẫu:OEIS2C
3	−3	Bản mẫu:OEIS2C	Bản mẫu:OEIS2C
3	−2	Bản mẫu:OEIS2C	Bản mẫu:OEIS2C
3	−1	Bản mẫu:OEIS2C	Bản mẫu:OEIS2C
3	1	Bản mẫu:OEIS2C	Bản mẫu:OEIS2C
3	2	Bản mẫu:OEIS2C	Bản mẫu:OEIS2C
3	5	Bản mẫu:OEIS2C
4	−3	Bản mẫu:OEIS2C	Bản mẫu:OEIS2C
4	−2	Bản mẫu:OEIS2C
4	−1	Bản mẫu:OEIS2C	Bản mẫu:OEIS2C
4	1	Bản mẫu:OEIS2C	Bản mẫu:OEIS2C
4	2	Bản mẫu:OEIS2C	Bản mẫu:OEIS2C
4	3	Bản mẫu:OEIS2C	Bản mẫu:OEIS2C
4	4	Bản mẫu:OEIS2C
5	−3	Bản mẫu:OEIS2C
5	−2	Bản mẫu:OEIS2C
5	−1	Bản mẫu:OEIS2C	Bản mẫu:OEIS2C
5	1	Bản mẫu:OEIS2C	Bản mẫu:OEIS2C
5	4	Bản mẫu:OEIS2C	Bản mẫu:OEIS2C
6	1	Bản mẫu:OEIS2C	Bản mẫu:OEIS2C

Ứ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

Bản mẫu:Tham khảo

Tham khảo

Bản mẫu:Chú thích
Bản mẫu:Chú thích tạp chí
Bản mẫu:Chú thích tạp chí
Bản mẫu:Chú thích tạp chí
Bản mẫu:Chú thích tạp chí
Bản mẫu:Chú thích sách
Bản mẫu:Chú thích tạp chí
Bản mẫu:Chú thích tạp chí
Bản mẫu:Chú thích sách
Bản mẫu:Chú thích sách
Bản mẫu:Chú thích tạp chí
Bản mẫu:Chú thích tạp chí
Bản mẫu:Chú thích sách
Dãy Lucas tại Bách khoa toàn thư Toán học Bản mẫu:En
<templatestyles src="Module:Citation/CS1/styles.css"></templatestyles> Bản mẫu:MathWorld
Bản mẫu:Chú thích web

↑ Xem tính liên hệ và chia hết này trong Bản mẫu:Harvard citation, Bản mẫu:Harvard citation or Bản mẫu:Harvard citation.
↑ ^2,0 ^2,1 Bản mẫu:Chú thích tạp chí
↑ Bản mẫu:Chú thích tạp chí
↑ Bản mẫu:Chú thích tạp chí
↑ Bản mẫu:Chú thích tạp chí
↑ Bản mẫu:Chú thích tạp chí

[1] Xem tính liên hệ và chia hết này trong Bản mẫu:Harvard citation, Bản mẫu:Harvard citation or Bản mẫu:Harvard citation.

[Yabuta-2] 2,0 ^2,1 Bản mẫu:Chú thích tạp chí

[3] Bản mẫu:Chú thích tạp chí

[BLS75-4] Bản mẫu:Chú thích tạp chí

[5] Bản mẫu:Chú thích tạp chí

[6] Bản mẫu:Chú thích tạp chí

[1]

[2]

[3]

[4]

[5]

[6]

Dãy Lucas

Mục lục

Hệ thức truy hồi

Ví dụ

Biểu thức tường minh

Nghiệm phân biệt

Nghiệm trùng nhau

Tính chất

Hàm sinh

Phương trình Pell

Quan hệ các dãy với tham số khác nhau

Quan hệ khác

Tính chia hết

Một số trường hợp cụ thể

Ứng dụng

Chú thích

Tham khảo

Bảng điều hướng

Dãy Lucas

Hệ thức truy hồi

Ví dụ

Biểu thức tường minh

Nghiệm phân biệt

Nghiệm trùng nhau

Tính chất

Hàm sinh

Phương trình Pell

Quan hệ các dãy với tham số khác nhau

Quan hệ khác

Tính chia hết

Một số trường hợp cụ thể

Ứng dụng

Chú thích

Tham khảo

Bảng điều hướng

Tìm kiếm