Делимость чисел Фибоначи.

[Руст]

Пусть $F_n$ ($F_0=0,F_1=1,F_{n+1}=F_n+F_{n-1}$) n-ое число Фибоначи.
1)Докажите, что если n нечётное, то $val_2(F_n)\le 1$ и все нечётные простые делители имеют вид $p\equiv 1\mod 4$.
2) Существует ли для любого k число n, что $2^k|F_n$?

[Nilenbert]

Ну со вторым всё очевидно. Покажем, что для любого $n \in N$ выполняется следующее: $2^{n+2}|F_{3\cdot 2^n}$
По индукции: $n=1:2^{1+2}=8|8=F_{3\cdot 1}$
Переход: Так как$F_{2n}=F_n(F_{n-1}+F_{n+1})$, то

$$\frac{F_{2n}}{F_n}=F_{n-1}+F_{n+1}=F_{n-1}+F_{n-1}+F_n\equiv F_n\pmod{2}$$

Тогда, $\frac{F_{3\cdot 2^{n+1}}}{F_{3\cdot 2^n}}\equiv F_{3\cdot 2^n}\equiv 0\pmod{2}$. Значит, $\frac{F_{3\cdot 2^{n+1}}}{F_{3\cdot 2^n}}$ - чётное число, следовательно $2^{n+3}|2F_{3\cdot 2^n}|F_{3\cdot 2^{n+1}}$.
А вообще, для любого $k\in N$, существует бесконечно много чисел Фибоначчи делящихся на $k$.

[Dandan]

Руст писал(а):

Пусть $F_n$ ($F_0=0,F_1=1,F_{n+1}=F_n+F_{n-1}$) n-ое число Фибоначи.
1)Докажите, что если n нечётное, то $val_2(F_n)\le 1$ и все нечётные простые делители имеют вид $p\equiv 1\mod 4$.
2) Существует ли для любого k число n, что $2^k|F_n$?

1) $F_{2n+1}=F_n^2+F_{n+1}^2$ отсюда следует утверждение для простых делителей. А что такое $val_2(F_n)$ ?

2) остатки периодически, так что для любого числа найдется фибоначчи, которое делится на это число. Может в вопросе делимость наоборот?

[Руст]

Можно точно указать на порядок, если n не делится на 3, то $v_2(F_n)=0$. Если n делится на 3, но не делится на 6, то $v_2(F_n)=1$, если n делится на 6, то $v_2(F_n)=v_2(n)+2$.
другая задача на делимость на нечётное простое число p. Докажите, что существует такое число $T(p)|p-\binom{5}{p}$, что $F_n$ делится на р тогда и только тогда, когда n делится на T(p). Для делящихся на p имеет место $v_p(F_n)\ge 1+v_p(n)$.

[maxal]

Руст в сообщении #193149 писал(а):

Докажите, что существует такое число $T(p)|p+\binom{5}{p}$, что $F_n$ делится на р тогда и только тогда, когда n делится на T(p). Для делящихся на p имеет место $v_p(F_n)\ge 1+v_p(n)$.

Wall в статье "Fibonacci series modulo m" 1960 года высказал гипотезу, что для всех $n$ кратных $T(p)$ выполняется равенство $v_p(F_n)= 1+v_p(n).$ Эта гипотеза по-прежнему является открытой проблемой.
Впрочем, простые $p>5$, дающие контрпример к этой гипотезе для $n=T(p)$ (не смотря на то, что их существование под вопросом), уже получили название Wall-Sun-Sun primes. Кстати, сами Wall, Sun и Sun изучали такие простые в связи с последней теоремой Ферма.

[Руст]

Интересные вещи откопал maxal. По всей видимости простое p=2 ($T(p)=2-\binom{2}{5}=3$) единственное Wall Sun-Sun простое. Как я уже писал, в случае $6|n$ выполняется$v_2(F_n)=2+v_2(n)$], к тому же для n=2 не выполняется первый случай теоремы Ферма.

[maxal]

Руст
Я забыл упомянуть, что Wall-Sun-Sun требуют $p>5$. Так что, $p=2$ не в счёт.