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

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

Примеры

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

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

$i$	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	…
$F_{i}$	0	1	1	2	3	5	8	13	21	34	55	89	144	233	377	610	987	1597	2584	…
$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) последовательности $\{F_{i}\mod m\}$ повторяются бесконечно, значит для $m=4$ период Пизано равен шести: $\pi (4)=6$.

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

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

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

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

Свойства

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

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

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

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

• Для всех положительных целых чисел $m$ справедливо неравенство $\pi (m)\leqslant 6\cdot m$, причём равенство в нём достигается только на числах вида $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. — (Популярные лекции по математике).