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

Некоторые константно-рекурсивные целочисленные последовательности

В математике последовательности Люка и представляют собой определенные константно-рекурсивные целочисленные последовательности , удовлетворяющие рекуррентному соотношению ${\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}$

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

Рекуррентные соотношения

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

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

и

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

Нетрудно показать, что для , ${\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}}}$

Вышеуказанные соотношения можно записать в матричной форме следующим образом:

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

Примеры

Начальные члены последовательностей Люка приведены в таблице: ${\displaystyle U_{n}(P,Q)}$ ${\displaystyle 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 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.}$

Отношения между последовательностями с разными параметрами

• Для любого числа c последовательности и с ${\displaystyle U_{n}(P',Q')}$ ${\displaystyle V_{n}(P',Q')}$

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

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

имеют тот же дискриминант, что и : ${\displaystyle U_{n}(P,Q)}$ ${\displaystyle V_{n}(P,Q)}$

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

• Для любого числа 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).}$

Другие отношения

Члены последовательностей Люка удовлетворяют соотношениям, которые являются обобщениями соотношений между числами Фибоначчи и числами Люка . Например: ${\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}\\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}}}$

Свойства делимости

Среди следствий то, что является кратным , т. е. последовательность является последовательностью делимости . Это подразумевает, в частности, что может быть простым только тогда, когда 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]

• Если нечетно , то делится . ${\displaystyle n\mid 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({\tfrac {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({\tfrac {D}{p}}\right)}$

Последний факт обобщает малую теорему Ферма . Эти факты используются в тесте простоты Люка–Лемера . Обратное к последнему факту не выполняется, так как не выполняется обратная теорема малой теоремы Ферма. Существует составное число n , взаимно простое с D и делящее , где . Такое составное число называется псевдопростым числом Люка . ${\displaystyle U_{l}}$ ${\displaystyle l=n-\left({\tfrac {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 ( х +1, х )  : х ⁿ  + 1

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

Приложения

• Последовательности Лукаса используются в вероятностных тестах Лукаса на псевдопростоту , которые являются частью широко используемого теста простоты Бейли–ПСВ .
• Последовательности Лукаса используются в некоторых методах доказательства простоты, включая тест Лукаса–Лемера–Ризеля , а также методы N+1 и гибридные методы N−1/N+1, такие как методы Брилхарта-Лемера-Селфриджа 1975 года. ^[4]
• LUC — это криптосистема с открытым ключом, основанная на последовательностях Лукаса ^[5] , которая реализует аналоги Эль-Гамаля (LUCELG), Диффи–Хеллмана (LUCDIF) и RSA (LUCRSA). Шифрование сообщения в LUC вычисляется как член определенной последовательности Лукаса, вместо использования модульного возведения в степень , как в RSA или Диффи–Хеллмана. Однако статья Блейхенбахера и др. ^[6] показывает, что многие из предполагаемых преимуществ безопасности LUC по сравнению с криптосистемами, основанными на модульном возведении в степень, либо отсутствуют, либо не столь существенны, как утверждается.

Программное обеспечение

Sagemath реализует и как и , соответственно. ^[7] ${\displaystyle U_{n}}$ ${\displaystyle V_{n}}$lucas_number1()lucas_number2()

Смотрите также

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

Примечания

1. О таких отношениях и свойствах делимости см. (Carmichael 1913), (Lehmer 1930) или (Ribenboim 1996, 2.IV).
2. Yabuta, M (2001). «Простое доказательство теоремы Кармайкла о примитивных делителях» (PDF) . Fibonacci Quarterly . 39 (5): 439–443. doi :10.1080/00150517.2001.12428701 . Получено 4 октября 2018 г. .
3. Bilu, Yuri; Hanrot, Guillaume; Voutier, Paul M.; Mignotte, Maurice (2001). "Существование примитивных делителей чисел Люка и Лемера" (PDF) . J. Reine Angew. Math . 2001 (539): 75–122. doi :10.1515/crll.2001.080. MR  1863855. S2CID  122969549.
4. Джон Бриллхарт ; Деррик Генри Лемер ; Джон Селфридж (апрель 1975 г.). «Новые критерии простоты и факторизации 2m ± 1». Математика вычислений . 29 (130): 620–647. doi : 10.1090/S0025-5718-1975-0384673-1 . JSTOR  2005583.
5. PJ Smith; MJJ Lennon (1993). "LUC: Новая система открытых ключей". Труды Девятого Международного симпозиума IFIP по компьютерной безопасности : 103–117. CiteSeerX 10.1.1.32.1835 . 
6. D. Bleichenbacher; W. Bosma; AK Lenstra (1995). "Некоторые замечания о криптосистемах на основе Lucas" (PDF) . Advances in Cryptology — CRYPT0' 95 . Lecture Notes in Computer Science. Vol. 963. pp. 386–396. doi : 10.1007/3-540-44750-4_31 . ISBN 978-3-540-60221-7.
7. "Комбинаторные функции - Комбинаторика". doc.sagemath.org . Получено 2023-07-13 .

Ссылки

• Кармайкл, РД (1913), «О числовых множителях арифметических форм α ⁿ ±β ⁿ », Annals of Mathematics , 15 (1/4): 30–70, doi :10.2307/1967797, JSTOR  1967797
• Lehmer, DH (1930). «Расширенная теория функций Лукаса». Annals of Mathematics . 31 (3): 419–448. Bibcode : 1930AnMat..31..419L. doi : 10.2307/1968235. JSTOR  1968235.
• Уорд, Морган (1954). «Простые делители повторяющихся последовательностей второго порядка». Duke Math. J . 21 (4): 607–614. doi :10.1215/S0012-7094-54-02163-8. hdl : 10338.dmlcz/137477 . MR  0064073.
• Сомер, Лоуренс (1980). «Свойства делимости первичных повторений Лукаса относительно простых чисел» (PDF) . Fibonacci Quarterly . 18 (4): 316–334. doi :10.1080/00150517.1980.12430140.
• Lagarias, JC (1985). "Множество простых чисел, делящих числа Люка, имеет плотность 2/3". Pac. J. Math . 118 (2): 449–461. CiteSeerX  10.1.1.174.660 . doi :10.2140/pjm.1985.118.449. MR  0789184.
• Ганс Ризель (1994). Простые числа и компьютерные методы факторизации . Прогресс в математике. Т. 126 (2-е изд.). Биркхойзер. С. 107–121. ISBN 0-8176-3743-5.
• Рибенбойм, Пауло; Макдэниел, Уэйн Л. (1996). «Квадратные члены в последовательностях Лукаса». J. Number Theory . 58 (1): 104–123. doi : 10.1006/jnth.1996.0068 .
• Joye, M.; Quisquater, J.-J. (1996). "Эффективное вычисление полных последовательностей Лукаса" (PDF) . Electronics Letters . 32 (6): 537–538. Bibcode :1996ElL....32..537J. doi :10.1049/el:19960359. Архивировано из оригинала (PDF) 2015-02-02.
• Рибенбойм, Пауло (1996). Новая книга рекордов простых чисел (электронная версия). Springer-Verlag , Нью-Йорк. 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). «Совершенные числа Фибоначчи и Люка». Rend. Circ Matem. Палермо . 49 (2): 313–318. doi :10.1007/BF02904236. S2CID  121789033.
• Ябута, М. (2001). «Простое доказательство теоремы Кармайкла о примитивных делителях» (PDF) . Fibonacci Quarterly . 39 (5): 439–443. doi :10.1080/00150517.2001.12428701.
• Бенджамин, Артур Т.; Куинн , Дженнифер Дж. (2003). Доказательства, которые действительно имеют значение: искусство комбинаторного доказательства . Dolciani Mathematical Expositions. Том 27. Математическая ассоциация Америки . стр. 35. ISBN 978-0-88385-333-7.
• Последовательность Люка в Энциклопедии математики .
• Вайсштейн, Эрик В. «Последовательность Лукаса». Математический мир .
• Вэй Дай . «Последовательности Лукаса в криптографии».