Математикадан Алматы қаласының олимпиадасы, 2008 жыл

Фибоначчи тізбегі берілген: ${{F}_{1}}={{F}_{2}}=1$ және барлық натурал $n > 1$ сандары үшін ${{F}_{n+1}}={{F}_{n}}+{{F}_{n-1}}$. ${{F}_{n}}={{2}^{k}}$ теңдігі үшін $k$ натурал саны табылатындай барлық $n$ натурал сандарын табыңыз.

Комментарий/решение

$Ответ: 1,2,3,6$

Заметим такой факт: $(F_{m},F_{n})=F_{(m,n)}$ (это легко доказывается с помощью индукции и этой известной формулы: $F_{x+y}=F_{x-1}F_{y}+F_{x}F_{y+1}$).

$F_{6}=8$, сейчас докажу что при $6<n$ не существует степень двойки. $(F_{6k+1},F_{6})=(F_{6k+5},F_{6})=F_{1}=1$,

$(F_{6k+2},F_{6})=(F_{6k+4},F_{6})=F_{2}=1$

$(F_{6k+3},F_{6})=F_{3}=2$ ($1<k$),из этого следует что числа $F_{6k+1},...,F_{6k+5}$ не делятся на 8, значит они не степень двойки.

Теперь рассмотрим $F_{6k}$. Если $k$ четное, $F_{6k}$ делится на $F_{4}=3$. Если $k$ делится на 3, $F_{6k}$ делится на $F_{9}=34$. Если $k$ имеет простой делитель больше $3$, его вид будет $6d-1$( или $6d+1$, но этот случай рассматривается аналогично). Тогда $F_{6k}$ делится на $F_{6d-1}$, но $F_{6d-1} $ имеет простой делитель не равный $ 2$ (это показано сверху). Это означает что $F_{6k}$ не может быть степенью двойки.