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

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

Примеры

Например, определим период Пизано при $m=4$. Пусть $F_i$ — $i$-е число Фибоначчи. $F_{i}modm$ — остаток от деления $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}modm$	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}modm\}$ повторяются бесконечно, значит для $m=4$ период Пизано равен шести: $\pi (4)=6$.

Последовательность, составленная из периодов Пизано, получила номер Шаблон:OEIS2C в 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})(\mathrm{mod}m)$ для некоторых $i⩽j$. Поэтому для всех натуральных k выполняется $x_{i+k}\equiv x_{j+k}(\mathrm{mod}m)$, то есть, последовательность периодична.

Свойства

• Если a и b взаимно просты, то $\pi (ab)=\mathrm{l}\mathrm{c}\mathrm{m}(\pi (a),\pi (b))$. Или, если разложить $m$ на простые множители: $m=p_1^{{\alpha }_1}\cdot p_2^{{\alpha }_2}\cdot \dots \cdot p_k^{{\alpha }_k}$, то $\pi (m)=\mathrm{l}\mathrm{c}\mathrm{m}(\pi (p_1^{{\alpha }_1}),\pi (p_2^{{\alpha }_2}),\dots ,\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⩾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(\mathrm{mod}5)$ число $\pi (p)$ является делителем $p-1$;
  • при $p\equiv \pm 2(\mathrm{mod}5)$ число $\pi (p)$ является делителем $2\cdot p+2$.

• Для всех положительных целых чисел $m$ справедливо неравенство $\pi (m)⩽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»
• Шаблон:Книга