Последовательность Лукаса

В математике , то Лукас последовательности и определенные постоянная рекурсии целые последовательности , удовлетворяющие рекуррентное соотношение${\ displaystyle U_ {n} (P, Q)}$${\ displaystyle V_ {n} (P, Q)}$

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

где и - фиксированные целые числа. Любая последовательность, удовлетворяющая этому рекуррентному соотношению, может быть представлена ​​как линейная комбинация последовательностей Люка и .${\ displaystyle P}$${\ displaystyle Q}$${\ displaystyle U_ {n} (P, Q)}$${\ displaystyle V_ {n} (P, Q)}$

В более общем смысле , Лукас последовательности и представляют собой последовательности полиномов в и с целыми коэффициентами.${\ displaystyle U_ {n} (P, Q)}$${\ displaystyle V_ {n} (P, Q)}$${\ displaystyle P}$${\ displaystyle Q}$

Известные примеры Лукас последовательностей включают числа Фибоначчей , число Мерсено , номер Пеллы , номер Лукаса , номер Якобсталь и супернабор чисел Ферма . Последовательности Лукаса названы в честь французского математика Эдуара Лукаса .

Отношения повторения [ править ]

Для двух целочисленных параметров P и Q последовательности Люка первого типа U _n ( P , Q ) и второго типа V _n ( P , Q ) определяются рекуррентными соотношениями :

${\ displaystyle {\ 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 {выравнивается}}}$

и

${\ Displaystyle {\ 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}}}$

Не трудно показать , что для ,${\ displaystyle n> 0}$

${\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}}}$

Примеры [ править ]

Начальные члены последовательностей Люка U _n ( P , Q ) и V _n ( P , Q ) приведены в таблице:

${\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}}}$

Явные выражения [ править ]

Характеристическое уравнение рекуррентного соотношения для последовательностей Люка и имеет вид:${\displaystyle U_{n}(P,Q)}$${\displaystyle V_{n}(P,Q)}$

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

Он имеет дискриминант и корни:${\displaystyle D=P^{2}-4Q}$

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

Таким образом:

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

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

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

Обратите внимание, что последовательность и последовательность также удовлетворяют рекуррентному соотношению. Однако это могут быть не целые последовательности.${\displaystyle a^{n}}$${\displaystyle b^{n}}$

Отчетливые корни [ править ]

Когда , a и b различны, и быстро проверяется, что${\displaystyle D\neq 0}$

${\displaystyle a^{n}={\frac {V_{n}+U_{n}{\sqrt {D}}}{2}}}$

${\displaystyle b^{n}={\frac {V_{n}-U_{n}{\sqrt {D}}}{2}}}$.

Отсюда следует, что члены последовательностей Люка могут быть выражены через a и b следующим образом

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

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

Повторный корень [ править ]

Случай возникает именно тогда, когда для некоторого целого S так, что . В этом случае легко найти, что${\displaystyle D=0}$${\displaystyle P=2S{\text{ and }}Q=S^{2}}$${\displaystyle a=b=S}$

${\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}\,}$.

Свойства [ править ]

Генерация функций [ править ]

Обычные производящие функции :

${\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}}}.}$

Последовательности с одинаковым дискриминантом [ править ]

Если последовательности Люка и имеют дискриминант , то последовательности, основанные на и где${\displaystyle U_{n}(P,Q)}$${\displaystyle V_{n}(P,Q)}$${\displaystyle D=P^{2}-4Q}$${\displaystyle P_{2}}$${\displaystyle Q_{2}}$

${\displaystyle P_{2}=P+2}$

${\displaystyle Q_{2}=P+Q+1}$

имеют один и тот же дискриминант: .${\displaystyle P_{2}^{2}-4Q_{2}=(P+2)^{2}-4(P+Q+1)=P^{2}-4Q=D}$

Уравнения Пелла [ править ]

Когда , последовательности Лукаса и удовлетворяют определенным уравнениям Пелла :${\displaystyle Q=\pm 1}$${\displaystyle U_{n}(P,Q)}$${\displaystyle V_{n}(P,Q)}$

${\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.}$

Другие отношения [ править ]

Условия Лукаса последовательностей удовлетворяют соотношениям , которые являются обобщением тех , между числами Фибоначчи и Люка . Например:${\displaystyle F_{n}=U_{n}(1,-1)}$ ${\displaystyle L_{n}=V_{n}(1,-1)}$

${\displaystyle {\begin{array}{r|l}{\text{General case}}&(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}\\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}}}$

Среди последствий - то, что последовательность является кратной , то есть последовательность является последовательностью делимости . Отсюда, в частности, следует, что он может быть простым только тогда, когда n простое. Другим следствием является аналог возведения в степень возведением в квадрат, который позволяет быстро вычислить для больших значений n . Более того, если , то - последовательность сильной делимости.${\displaystyle U_{km}(P,Q)}$${\displaystyle U_{m}(P,Q)}$${\displaystyle (U_{m}(P,Q))_{m\geq 1}}$${\displaystyle U_{n}(P,Q)}$${\displaystyle U_{n}(P,Q)}$${\displaystyle \gcd(P,Q)=1}$${\displaystyle (U_{m}(P,Q))_{m\geq 1}}$

Другие свойства делимости следующие: ^[1]

• Если n / m нечетное, то делится .${\displaystyle V_{m}}$${\displaystyle V_{n}}$
• Пусть N целое число , взаимно простое с 2 Q . Если существует наименьшее положительное целое число r, для которого N делится , то набор n, для которого N делится, является в точности множеством, кратным r .${\displaystyle U_{r}}$${\displaystyle U_{n}}$
• Если P и Q четные, то всегда четные, кроме .${\displaystyle U_{n},V_{n}}$${\displaystyle U_{1}}$
• Если P четно, а Q нечетно, то четность равна n и всегда четна.${\displaystyle U_{n}}$${\displaystyle V_{n}}$
• Если P нечетно, а Q четно, то всегда нечетные для .${\displaystyle U_{n},V_{n}}$${\displaystyle n=1,2,\ldots }$
• Если P и Q нечетные, то четные тогда и только тогда, когда n кратно 3.${\displaystyle U_{n},V_{n}}$
• Если p - нечетное простое число, то (см. Символ Лежандра ).${\displaystyle U_{p}\equiv \left({\frac {D}{p}}\right),V_{p}\equiv P{\pmod {p}}}$
• Если p нечетное простое число и делит P и Q , то p делится для каждого .${\displaystyle U_{n}}$${\displaystyle n>1}$
• Если p нечетное простое число и делит P, но не Q , то p делится тогда и только тогда, когда n четно.${\displaystyle U_{n}}$
• Если p нечетное простое число и делит не P, а Q , то p никогда не делится на .${\displaystyle U_{n}}$${\displaystyle n=1,2,\ldots }$
• Если p нечетное простое число и делит не PQ, а D , то p делится тогда и только тогда, когда p делит n .${\displaystyle U_{n}}$
• Если p нечетное простое число и не делит PQD , то p делит , где .${\displaystyle U_{l}}$${\displaystyle l=p-\left({\frac {D}{p}}\right)}$

Последний факт обобщает малую теорему Ферма . Эти факты используются в тесте простоты Лукаса – Лемера . Обратное к последнему факту неверно, как и обратное к малой теореме Ферма. Существует составное n, взаимно простое с D и делящее , где . Такая композиция называется псевдопростой Люка .${\displaystyle U_{l}}$${\displaystyle l=n-\left({\frac {D}{n}}\right)}$

Главный фактор термина в последовательности Лукаса , который не делится на более ранний члена в последовательности называется примитивным . Теорема Кармайкла утверждает, что все, кроме конечного числа членов в последовательности Лукаса, имеют примитивный простой множитель . ^[2] Действительно, Кармайкл (1913) показал, что если D положительно и n не равно 1, 2 или 6, то имеет примитивный простой множитель. В случае отрицательного значения D глубокий результат Билу, Ханро, Вотье и Миньотта ^[3] показывает, что если n > 30, то имеет примитивный простой множитель и определяет все случаи${\displaystyle U_{n}}$${\displaystyle U_{n}}$${\displaystyle U_{n}}$ не имеет примитивного простого множителя.

Конкретные имена [ править ]

Последовательности Лукаса для некоторых значений P и Q имеют определенные имена:

U _n (1, −1)  : числа Фибоначчи

V _n (1, −1)  : числа Люка

U _n (2, −1)  : числа Пелла

V _n (2, −1)  : числа Пелл-Люка (сопутствующие числа Пелла)

U _n (1, −2)  : числа Якобсталя

V _n (1, −2)  : числа Якобсталя-Лукаса

U _n (3, 2)  : числа Мерсенна 2 ⁿ  - 1

V _n (3, 2)  : числа в форме 2 ⁿ  + 1, которые включают числа Ферма . ^[2]

U _n (6, 1)  : квадратные корни из квадратных треугольных чисел .

U _n ( x , −1)  : полиномы Фибоначчи

V _n ( x , −1)  : многочлены Люка

U _n (2 x , 1)  : многочлены Чебышева второго рода

V _n (2 x , 1)  : многочлены Чебышева первого рода, умноженные на 2

U _n ( x +1, x )  : объединяет базу x

V _n ( x +1, x )  : x ⁿ + 1

Некоторые последовательности Лукаса имеют записи в Он-лайн энциклопедии целочисленных последовательностей :

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

Приложения [ править ]

• Последовательности Лукаса используются в вероятностных тестах псевдоперминала Лукаса , которые являются частью обычно используемого критерия простоты Бейли-PSW .
• Последовательности Лукаса используются в некоторых методах доказательства простоты, включая тест Лукаса-Лемера-Ризеля , а также N + 1 и гибридный N-1 / N + 1 методы, такие как методы Brillhart-Lehmer-Selfridge 1975 ^[4]
• LUC является открытым ключом криптосистемы на основе Lucas последовательностей ^[5] , который реализует аналоги ElGamal (LUCELG), Диффи-Хеллмана (LUCDIF) и RSA (LUCRSA). Шифрование сообщения в LUC вычисляется как член определенной последовательности Лукаса, вместо использования модульного возведения в степень, как в RSA или Диффи-Хеллмана. Однако в статье Bleichenbacher et al. ^[6] показывает, что многие из предполагаемых преимуществ безопасности LUC над криптосистемами, основанными на модульном возведении в степень, либо отсутствуют, либо не столь существенны, как заявлено.

См. Также [ править ]

• Лукас псевдопрайм
• Псевдопросто Фробениуса
• Псевдопреступление Сомера – Лукаса

Примечания [ править ]

Ссылки [ править ]

• Кармайкл, РД (1913), "О численных факторов арифметических форм & alpha ; ^п ± & beta ; ^п ", Анналы математики , 15 (1/4): 30-70, DOI : 10,2307 / 1967797 , JSTOR  1967797
• Лемер, Д.Х. (1930). «Расширенная теория функций Лукаса». Анналы математики . 31 (3): 419–448. Bibcode : 1930AnMat..31..419L . DOI : 10.2307 / 1968235 . JSTOR  1968235 .
• Уорд, Морган (1954). «Простые делители повторяющихся последовательностей второго порядка». Duke Math. Дж . 21 (4): 607–614. DOI : 10.1215 / S0012-7094-54-02163-8 . hdl : 10338.dmlcz / 137477 . Руководство по ремонту  0064073 .
• Сомер, Лоуренс (1980). «Свойства делимости первичных повторений Лукаса относительно простых чисел» (PDF) . Ежеквартальный отчет Фибоначчи . 18 : 316.
• Лагариас, JC (1985). «Множество простых чисел, делящих числа Лукаса, имеет плотность 2/3». Pac. J. Math . 118 (2): 449–461. DOI : 10,2140 / pjm.1985.118.449 . Руководство по ремонту  0789184 .
• Ханс Ризель (1994). Простые числа и компьютерные методы факторизации . Успехи в математике. 126 (2-е изд.). Birkhäuser. С. 107–121. ISBN 0-8176-3743-5.
• Рибенбойм, Пауло; Макдэниел, Уэйн Л. (1996). «Квадратные члены в последовательностях Лукаса». J. Теория чисел . 58 (1): 104–123. DOI : 10,1006 / jnth.1996.0068 .
• Joye, M .; Quisquater, J.-J. (1996). «Эффективное вычисление полных последовательностей Лукаса» (PDF) . Письма об электронике . 32 (6): 537–538. DOI : 10.1049 / эл: 19960359 . Архивировано из оригинального (PDF) 02 февраля 2015 года.
• Рибенбойм, Пауло (1996). Новая книга рекордов простых чисел (электронная книга). Спрингер-Верлаг , Нью-Йорк. DOI : 10.1007 / 978-1-4612-0759-7 . ISBN 978-1-4612-0759-7.
• Рибенбойм, Пауло (2000). Мои числа, мои друзья: Популярные лекции по теории чисел . Нью-Йорк: Springer-Verlag . С. 1–50. ISBN 0-387-98911-0.
• Лука, Флориан (2000). «Совершенные числа Фибоначчи и Лукаса». Ренд. Circ Matem. Палермо . 49 (2): 313–318. DOI : 10.1007 / BF02904236 . S2CID  121789033 .
• Ябута, М. (2001). «Простое доказательство теоремы Кармайкла о примитивных делителях» (PDF) . Ежеквартальный отчет Фибоначчи . 39 : 439–443.
• Бенджамин, Артур Т .; Куинн, Дженнифер Дж. (2003). Доказательства, которые действительно важны: искусство комбинаторного доказательства . Математические экспозиции Дольчиани. 27 . Математическая ассоциация Америки . п. 35 . ISBN 978-0-88385-333-7.
• Последовательность Лукаса в энциклопедии математики .
• Вайсштейн, Эрик В. «Последовательность Лукаса» . MathWorld .
• Вэй Дай . «Последовательности Лукаса в криптографии» .