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

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

Приклади

Послідовність Фібоначчі за модулем будь-якого цілого додатного числа m періодична, оскільки серед перших $m^{2}+1$ пар чисел знайдуться дві рівні пари $(x_{i},x_{i+1})=(x_{j},x_{j+1})$ для деяких $i\leq j$. Тому для всіх цілих k виконується $x_{i+k}=x_{j+k}$, тобто, послідовність періодична.

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

0, 1, 1, 2, 3, 1, 0, 1, 1, 2, 3, 1, 0, 1, 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 {HCK} \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 {HCK} (\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$ — просте число, то справедливі такі твердження:
  • при $p\equiv \pm 1{\pmod {5}}$ число $\pi (p)$ є дільником $p-1$,
  • при $p\equiv \pm 2{\pmod {5}}$ число $\pi (p)$ є дільником $2p+2$.

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

Посилання

• Charles W. Campbell II, «The Period of the Fibonacci Sequence Modulo j» [Архівовано 19 лютого 2018 у Wayback Machine.], Math 399 Spring 2007
• Marc Renault, «The Fibonacci sequence modulo m»
• Н. Н. Воробьёв. Числа Фибоначчи. — Наука, 1978. — Т. 39. — (Популярные лекции по математике).