Последовательность Фибоначчи как ЛРП или что делать, если хочется найти период у бесконечной последовательности?

2025-06-20 в 18:14, admin, рубрики: ЛРП, порядок многочлена, последовательность фибоначчи, рекурренты

Что же такое ЛРП или линейная рекуррентная последовательность? Последовательность, которую можно задать рекуррентным уравнением $s_{n+k}=a_{k-1}s_{n+k-1} + ... + a_{0}s_{k}$ , где коэффициенты - фиксированные элементы поля и есть ЛРП над полем .

Сопровождающая матрица ЛРП выглядит следующим образом:

$A=begin{pmatrix} 0 & 0 & 0 & cdots & 0 & a_0 \ 1 & 0 & 0 & cdots & 0 & a_1 \ 0 & 1 & 0 & cdots & 0 & a_2 \ vdots & vdots & vdots & ddots & vdots & vdots \ 0 & 0 & 0 & cdots & 1 & a_{k-1} end{pmatrix}$ .

Её характеристический многочлен: $f(x)=|xE - A|=x^k - a_{k-1}x^{k-1} - ldots - a_1x_1 - a_0$

Упражняться в теории ЛРП мы будем не на случайных примерах, а искать так называемый период Пизано, то есть период последовательности Фибоначчи по простому модулю. Про сам этот период написано довольно много, но моё домашнее задание было достаточно конкретным, продемонстрировать связь порядка и периода. Я же, в качестве бонуса, опишу стратегию поведения и для случая когда правило "порядок это период" не актуально.

mod 2

Над полем характеристический многочлен имеет следующий вид: . Известно, что минимальный период ЛРП с неприводимым характеристическим многочленом (а он неприводим) при ненулевом начальном состоянии равен порядку многочлена . Есть два способа найти порядок:

Порядок неприводимого характеристического многочлена совпадает с порядком сопровождающей матрицы как элемента группы .
Порядок неприводимого многочлена делит , так как это всегда период (совпадает с порядком примитивного многочлена).

Второй быстрее. - число простое, нетрудно, используя матрицу, убедиться, что период в точности 3.

$A=begin{pmatrix} 0 & 1 \ 1 & 1 end{pmatrix};$ $A^2=begin{pmatrix} 1 & 1 \ 1 & 0 end{pmatrix};$ $A^3=begin{pmatrix} 1 & 0 \ 0 & 1 end{pmatrix}=E.$

Также продемонстрируем это выписав саму последовательность Ф: 011011011011...

mod 3

Над полем характеристический многочлен уже имеет вид: . Опять же по теории искомый порядок делитель числа . Убеждаемся, что ни 2, ни 4 не подходят, то бишь искомый период ЛРП 8. Продемонстрируем это с помощью матриц:

$A=begin{pmatrix} 0 & 1 \ 1 & 1 end{pmatrix};$ $A^2=begin{pmatrix} 1 & 1 \ 1 & 2 end{pmatrix};$ $A^3=begin{pmatrix} 1 & 2 \ 2 & 0 end{pmatrix};$ $A^4=begin{pmatrix} 2 & 0 \ 0 & 2 end{pmatrix};$ $A^5=begin{pmatrix} 0 & 2 \ 2 & 2 end{pmatrix};$

$A^6=begin{pmatrix} 2 & 2 \ 2 & 1 end{pmatrix};$ $A^7=begin{pmatrix} 2 & 1 \ 1 & 0 end{pmatrix};$ $A^8=begin{pmatrix} 1 & 0 \ 0 & 1 end{pmatrix}=E.$

Снова продемонстрируем это выписав саму последовательность Ф: 01120221011...

mod 11

Над полем характеристический многочлен тоже имеет вид: , отличие в том, что теперь он приводим. . Что же делать в таком случае, ведь ранее приводимые методы работают только для неприводимых многочленов, в этом случае применима следующая теорема:

Пусть таковы, что, если , ord() = , тогда ord(), где = НОК().

Порядки же теперь будем искать, так сказать, "по старинке". То есть будем искать минимальные и такие, что $x^{l_1} - 1$ и $x^{l_2} - 1$ делятся на и соответственно, причём достаточно перебирать только делители числа . Путём перебора нетрудно получить, что , а . Следовательно, .

!!! В переборе также может помочь то, что порядок многочлена равен порядку его корня в мультипликативной группе соответствующего поля $F_{p^n}$ (в нашем случае p = 11, а n = 1).

mod 5

А теперь перейдём к самому интересному, на мой взгляд, случаю. Тут мы немного отойдём от конечным полей и обратимся к особенностям самой последовательности.

Так в чём же проблема?

Проблема в том, что над полем характеристический многочлен является полным квадратом: , а на такой случай у нас теории нет.

Для ответа на вопрос какой же всё-таки период обратимся к истокам. Доказательство формулы можно найти здесь https://www.fq.math.ca/Scanned/1-2/robinson.pdf. Мне оно кажется исчерпывающим и не требующим дополнительных комментариев, так что ограничимся лишь формулировкой (Я немного перефразирую автора дабы не заставлять читателя предварительно знакомиться с обозначениями оригинальной статьи).

Пусть - индекс первого, отличного от начального элемента, нуля в последовательности Фибоначчи , где модуль по которому рассматривается последовательность, тогда, если $(f_{n(N) + 1}, N)=1$ , то , где $f_{n(N) + 1}^{m(N)} equiv 1$ (mod ).

Посмотрим на примере при N = 5: 0112303314044320224101123

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

(mod 5)
(mod 5)
(mod 5)
(mod 5) .

То есть период нашей последовательности .

Оказывается

над полем эквивалентно системе сравнений

$begin{cases} -1 equiv -2y text{ mod p} \ -1 equiv y^2 text{ mod p} \ -2y equiv y^2 text{ mod p} end{cases} Rightarrow -2 equiv y text{ mod p, т.к. } y<p Rightarrow (y, p)=1, text{ то есть } -1 equiv 4 text{ mod p},$