Фибоначчи...

[Профессор Снэйп]

Берём произвольные $a_0, a_1 \in \mathbb{Z}_m$ и далее как обычно: $a_{t+2} = a_t + a_{t+1}$ для всех $t \geqslant 0$.

1) Доказать, что $a_0 = a_n$ и $a_1 = a_{n+1}$ для некоторого целого $n \geqslant 0$.

2) Выразить минимальное такое $n$ через $a_0$ и $a_1$ (ну и через $m$, естественно).

3) То же самое, только $\sigma_0, \sigma_1 \in S_n$ и $\sigma_{t+2} = \sigma_t \sigma_{t+1}$.

[Sonic86]

Ну формула Бине будет верна и в $\mathbb{Z}_m$, и из нее сразу следует 1 (возможно, для этого понадобиться $\mathbb{Z}[\sqrt{5}]$, но ничего страшного...)...

[ИСН]

Однако период выражается через m довольно непросто (как минимум, разложить его на простые множители придётся).

[Руст]

Обозначьте $k=(a_0,a_1),m_1=\frac{m}{k}, a_0'=\frac{a_0}{k},a_1'=\frac{a_1}{k}$. Тогда задача сводится к модулю $m_1$ с взаимно простыми начальными данными. Соответственно все остальные последовательные $(a_n,a_{n+1})=(a_{n-1},a_n)=...(a_0,a_1)$ так же взаимно просты.
Любая такая последовательность представляется в виде суммы $a_n=a_0b_n+a_1c_n$, где $b_n,c_n$ удовлетворяют тому же рекурентному соотношению, только с другими начальными условиями $b_0=1,b_1=0,c_0=0,c_1=1.$ Так как $c_n=b_{n+1}$ то у них период по любому модулю общий. Отсюда получается, что достаточно найти периоды для чисел Фибоначчи $c_n$. Период не зависит от начальных данных (лишь бы они были взаимно просты).
Учитывая китайскую теорему об остатках:

$$Z/mZ=\sum_i Z/p_i^{k_i}Z$$

все сводится к случаю когда $m_i=p_i^{k_i}$ -степени простых чисел. Период будет наименьшим общим кратным периодов для степеней простых чисел. Представим числа Фибоначчи по формуле

$$F_n=\frac{q^n-(-q)^{-n}}{\sqrt 5}, q=\frac{1+\sqrt 5}{2}.$$

Рассмотрим случай $m=p$. В случае $p=5$ наименьшее n, для которого $5|F_n$ равно 5. Однако $F_6=8=3\mod 5$, поэтому период последовательности 20. Учитывая, что $5^2\not |F_5$ получается, что период по модулю $5^k$ есть $4*5^k$. Случай $p=2$ так же немного особый и находится период по модулю $2^k$ равным $3*2^{k-1}$.
$p\not =5,2$. Вычисляем $F_p=\frac{(1+\sqrt 5)^p-(1-\sqrt 5)^p}{2^p\sqrt 5}=5^{(p-1)/2}\mod p$. Когда $5$ квадратичный вычет легко получается, что $p|F_{p-1}$, т.е. $p-1$ - период ($F_{p-1}=0,F_p=1$) по модулю $p$. Истинный период может быть меньше. По крайней мере имеются случаи, когда период делимости меньше. Когда $5$ квадратичный невычет по модулю $p$ получается $p|F_{p+1}, F_{p+2}=-1$ , поэтому истинный период $2(p+1)/k$ или $k$ - нечетное число. Если $T_p$ период по модулю $p$ и $F_{T_p},F_{T_p+1}-1$ оба не делятся на $p^2$, то период по модулю $p^k$ будет равен $p^{k-1}T_p$ (это легко доказывается). Пока не найдено простое число для которого это условие не выполняется и есть гипотеза, что это всегда так. После нахождения периода по всем примарным компонентам общий период находится как наименьшее общее кратное.
Случай с $\sigma$ так же разлагается на примарные компоненты. Только при рассмотрении по модулю $p^k$ для $\sigma$ приходим к рассмотрению чисел Фибоначчи по модулю $p^{k-1}(p-1)$.

[svv]

Профессор Снэйп писал(а):

1) Доказать, что $a_0 = a_n$ и $a_1 = a_{n+1}$ для некоторого целого $n \geqslant 0$.

Пары последовательных элементов $(a_t, a_{t+1})$ принимают конечное число значений (не более, чем $m^2$), поэтому будут повторяться: существуют $k$ и $l>k$ такие, что $(a_k, a_{k+1})=(a_{l}, a_{l+1})$. Если $k=0$, доказано. Иначе $(a_{k-1}, a_{k})=(a_{l-1}, a_{l})$ и далее по индукции, пока индекс первого элемента в левой части не станет $0$.

[Naf2000]

жесть http://oeis.org/A001175

[Naf2000]

$\mathbb{Z}_n$
Нда... что удалось получить если $n=p$ - простое число:
Обозначим $h(p)$ - минимальный индекс в последовательности Фибоначчи для которого $F_p$ делится на $p$, тогда
1. $h(p)\leqslant p+1$
2. длина цикла $\pi(p)=q(p)h(p)$, где
$q(p)=4$, если $h(p)$-нечетное
$q(p)=1$ или $2$, если $h(p)$-четное
3. всего таких циклов (я их назвал "главными" циклами) $(p-1)/q(p)$
но "главными" циклами не все описывается, есть еще другие, вот с ними засада, например циклы для $p=11$:

> 0
> 1 2 3 5 8 2 10 1 0 1
> 2 4 6 10 5 4 9 2 0 2
> 3 6 9 4 2 6 8 3 0 3
> 4 8 1 9 10 8 7 4 0 4
> 5 10 4 3 7 10 6 5 0 5
> 6 1 7 8 4 1 5 6 0 6
> 7 3 10 2 1 3 4 7 0 7
> 8 5 2 7 9 5 3 8 0 8
> 9 7 5 1 6 7 2 9 0 9
> 10 9 8 6 3 9 1 10 0 10
> 5 9 3 1 4
> 9 6 4 10 3 2 5 7 1 8
> 10 7 6 2 8

впрочем все это позже я нашел в интернете ((