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

Что же такое ЛРП или линейная рекуррентная последовательность? Последовательность, которую можно задать рекуррентным уравнением , где коэффициенты — фиксированные элементы поля и есть ЛРП над полем .

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

.

Её характеристический многочлен:

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

mod 2

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

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

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

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

mod 3

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

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

mod 11

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

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

Порядки же теперь будем искать, так сказать, «по старинке». То есть будем искать минимальные и такие, что и делятся на и соответственно, причём достаточно перебирать только делители числа . Путём перебора нетрудно получить, что , а . Следовательно, .

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

mod 5

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

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

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

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

• Пусть — индекс первого, отличного от начального элемента, нуля в последовательности Фибоначчи , где модуль по которому рассматривается последовательность, тогда, если , то , где (mod ).

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

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

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

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

Оказывается

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

что возможно лишь при . То есть мы рассмотрели все возможные случаи!

Источник: habr.com