Городская олимпиада по математике среди физ-мат школ Алматы, 2009 год

Дана последовательность Фибоначчи: $F_{1} =F_{2} =1$, $F_{n+1} =F_{n} +F_{n-1} $ для всех натуральных чисел $n > 1$. Определите все натуральные числа $n$, для которых существует натуральное число $k$ такое, что $F_{n} =2^{k}$.

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

$Ответ: 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}$ не может быть степенью двойки.