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

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

Примеры

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

Например, по модулю $4$ последовательность Фибоначчи выглядит как

0, 1, 1, 2, 3, 1, 0, 1, …

и поэтому $\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

Свойства

• Если a и b взаимно просты, то $\pi(ab)=\mathrm{HOK}\left(\pi(a), \pi(b)\right)$. Или если $m=p_{1}^{\alpha_{1}}\cdot p_{2}^{\alpha_{2}} \cdot\ldots\cdot p_{k}^{\alpha_{k}}$, то $\pi(m)=\mathrm{HOK}(\pi(p_{1}^{\alpha_{1}}), \pi(p_{2}^{\alpha_{2}}),\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 ≥ 1 выполняется $\pi(p^k)|p^{k-1}\cdot\pi(p)$. Более того, для всех точных степеней простых чисел от 1 до миллиона выполнено равенство $\pi(p^k)=p^{k-1}\cdot\pi(p)$. Но до сих пор неизвестно, на всегда ли выполнено это равенство, и существуют ли такое p, что $\pi(p^2)=\pi(p)$.

• Если $p$ — нечётное простое число, то $\pi(p)$ является делителем $p-\left(\frac{p}{5}\right)$, где $\left(\frac{p}{5}\right)$ — символ Лежандра. В частности, справедливы следующие утверждения:^[1]
  • при $p\equiv\pm 1\pmod 5$ выполняется $\pi(p)|(p-1)$,
  • при $p\equiv\pm 2\pmod 5$ выполняется $\pi(p)|(p+1)$.

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

Примечания

1. ↑ Используя формулу Бине можно найти в явном виде $F_{p-1},\; F_{p},\; F_{p+1}$, точнее при $p\equiv\pm 1\pmod 5$ (то есть, $p$ — квадратичный вычет по модулю 5) имеем $F_{p-1} \equiv 0,\; F_{p}\equiv1,\; F_{p+1}\equiv1 \pmod p$, а при $p\equiv\pm 2\pmod 5$ (то есть, $p$ — квадратичный невычет по модулю 5) имеем $F_{p-1} \equiv1,\; F_{p}\equiv-1,\; F_{p+1}\equiv1\pmod p$, откуда следуют соотношения делимости периодов.

Ссылки

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