2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Фибоначчи...
Сообщение21.02.2011, 03:29 
Заморожен
Аватара пользователя


18/12/07
8774
Новосибирск
Берём произвольные $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}$.

 Профиль  
                  
 
 Re: Фибоначчи...
Сообщение21.02.2011, 07:44 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Фибоначчи...
Сообщение21.02.2011, 10:11 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Фибоначчи...
Сообщение21.02.2011, 10:35 
Заслуженный участник


09/02/06
4401
Москва
Обозначьте $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)$.

 Профиль  
                  
 
 Re: Фибоначчи...
Сообщение21.02.2011, 14:09 
Заслуженный участник
Аватара пользователя


23/07/08
10910
Crna Gora
Профессор Снэйп писал(а):
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$.

 Профиль  
                  
 
 Re: Фибоначчи...
Сообщение22.02.2011, 10:23 


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

 Профиль  
                  
 
 Re: Фибоначчи...
Сообщение01.03.2011, 10:02 


05/10/10
71
$\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

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 7 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group