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

Період Пізано $\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, 1, 2, 3, 1, 0, 1, 1 ...

і тому $\pi (4)=6$.

Послідовність періодів Пізано починається так (Шаблон: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{H}\mathrm{C}\mathrm{K}(\pi (a),\pi (b))$. Або якщо $m=p_1^{{\alpha }_1}\cdot p_2^{{\alpha }_2}\cdot \dots \cdot p_k^{{\alpha }_k}$, то $\pi (m)=\mathrm{H}\mathrm{C}\mathrm{K}(\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)$. Більше того, для всіх точних степенів простих чисел від 1 до мільйона виконано рівність $\pi (p^k)=p^{k-1}\cdot \pi (p)$. Але досі невідомо, чи на завжди виконано цю рівність, і чи існує таке p, що $\pi (p^2)=\pi (p)$.

• Якщо $p$ — просте число, то справедливі такі твердження:
  • при $p\equiv \pm 1(\mathrm{mod}5)$ число $\pi (p)$ є дільником $p-1$,
  • при $p\equiv \pm 2(\mathrm{mod}5)$ число $\pi (p)$ є дільником $2p+2$.

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

Посилання

• Charles W. Campbell II, «The Period of the Fibonacci Sequence Modulo j» Шаблон:Webarchive, Math 399 Spring 2007
• Marc Renault, «The Fibonacci sequence modulo m»
• Шаблон:Книга-ру