Период Пизано

Период Пизано ${\displaystyle \pi (m)}$ — это длина периода последовательности Фибоначчи по модулю заданного натурального числа m.

Примеры

Например, определим период Пизано при ${\displaystyle m=4}$. Пусть ${\displaystyle F_{i}}$ — ${\displaystyle i}$-е число Фибоначчи. ${\displaystyle F_{i}\mod m}$ — остаток от деления ${\displaystyle i}$-го числа Фибоначчи на число ${\displaystyle m}$. Заполнив следующую таблицу,

Определение ${\displaystyle \pi (m)}$ при ${\displaystyle m=4}$

${\displaystyle i}$	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	…
${\displaystyle F_{i}}$	0	1	1	2	3	5	8	13	21	34	55	89	144	233	377	610	987	1597	2584	…
${\displaystyle F_{i}\mod m}$	0	1	1	2	3	1	0	1	1	2	3	1	0	1	1	2	3	1	0	…

заметим, что первые шесть чисел (0, 1, 1, 2, 3, 1) последовательности ${\displaystyle \{F_{i}\mod m\}}$ повторяются бесконечно, значит для ${\displaystyle m=4}$ период Пизано равен шести: ${\displaystyle \pi (4)=6}$.

Последовательность, составленная из периодов Пизано, получила номер A001175 в OEIS, ей начало показано в следующей таблице.

${\displaystyle m}$	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
${\displaystyle \pi (m)}$	1	3	8	6	20	24	16	12	24	60	10	24	28	48	40	24

Периодичность

Последовательность Фибоначчи по модулю любого натурального числа ${\displaystyle m}$ периодична, так как среди первых ${\displaystyle m^{2}+1}$ пар чисел найдутся две равные пары ${\displaystyle (x_{i},x_{i+1})\equiv (x_{j},x_{j+1}){\pmod {m}}}$ для некоторых ${\displaystyle i\leqslant j}$. Поэтому для всех натуральных k выполняется ${\displaystyle x_{i+k}\equiv x_{j+k}{\pmod {m}}}$, то есть, последовательность периодична.

Свойства

• Если a и b взаимно просты, то ${\displaystyle \pi (ab)=\mathrm {lcm} \left(\pi (a),\pi (b)\right)}$. Или, если разложить ${\displaystyle m}$ на простые множители: ${\displaystyle m=p_{1}^{\alpha _{1}}\cdot p_{2}^{\alpha _{2}}\cdot \ldots \cdot p_{k}^{\alpha _{k}}}$, то ${\displaystyle \pi (m)=\mathrm {lcm} \left(\pi (p_{1}^{\alpha _{1}}),\pi (p_{2}^{\alpha _{2}}\right),\ldots ,\pi (p_{k}^{\alpha _{k}}))}$ (следствие китайской теоремы об остатках).

• ${\displaystyle \pi (m)=\sigma (m)\cdot \sigma _{0}(m)}$, где за ${\displaystyle \sigma (m)\;}$ обозначено количество нулей в периоде, а за ${\displaystyle \sigma _{0}(m)\;}$ обозначен индекс первого нуля (не считая ${\displaystyle F_{0}}$). Более того, известно что ${\displaystyle \sigma (m)\in \{1,2,4\}}$.

• Для простого числа ${\displaystyle p}$ и целого числа ${\displaystyle k\geqslant 1}$ выполняется ${\displaystyle \pi (p^{k})|p^{k-1}\cdot \pi (p)}$. Более того, равенство ${\displaystyle \pi (p^{k})=p^{k-1}\cdot \pi (p)}$ выполнено для всех^[1] простых ${\displaystyle p}$, меньших ${\displaystyle 2^{64}}$, и неизвестно, существуют ли вообще такие простые числа, для которых оно не выполняется (см. простое число Уолла — Суня — Суня).

• Если ${\displaystyle p}$ — простое число, то справедливы следующие утверждения:
  • при ${\displaystyle p\equiv \pm 1{\pmod {5}}}$ число ${\displaystyle \pi (p)}$ является делителем ${\displaystyle p-1}$;
  • при ${\displaystyle p\equiv \pm 2{\pmod {5}}}$ число ${\displaystyle \pi (p)}$ является делителем ${\displaystyle 2\cdot p+2}$.

• Для всех положительных целых чисел ${\displaystyle m}$ справедливо неравенство ${\displaystyle \pi (m)\leqslant 6\cdot m}$, причём равенство в нём достигается только на числах вида ${\displaystyle m=2\cdot 5^{k}}$.

Примечания

Ссылки

• Charles W. Campbell II, «The Period of the Fibonacci Sequence Modulo j»
• Marc Renault, «The Fibonacci Sequence Modulo m»
• Н. Н. Воробьёв. Числа Фибоначчи. — Наука, 1978. — Т. 39. — (Популярные лекции по математике).

Эта страница в последний раз была отредактирована 18 апреля 2024 в 19:13.