Loading [MathJax]/jax/output/SVG/jax.js

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


Дана последовательность Фибоначчи: F1=F2=1, Fn+1=Fn+Fn1 для всех натуральных чисел n>1. Определите все натуральные числа n, для которых существует натуральное число k такое, что Fn=2k.
посмотреть в олимпиаде

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

  2
3 года 10 месяца назад #

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

Заметим такой факт: (Fm,Fn)=F(m,n) (это легко доказывается с помощью индукции и этой известной формулы: Fx+y=Fx1Fy+FxFy+1).

F6=8, сейчас докажу что при 6<n не существует степень двойки. (F6k+1,F6)=(F6k+5,F6)=F1=1,

(F6k+2,F6)=(F6k+4,F6)=F2=1

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

Теперь рассмотрим F6k. Если k четное, F6k делится на F4=3. Если k делится на 3, F6k делится на F9=34. Если k имеет простой делитель больше 3, его вид будет 6d1( или 6d+1, но этот случай рассматривается аналогично). Тогда F6k делится на F6d1, но F6d1 имеет простой делитель не равный 2 (это показано сверху). Это означает что F6k не может быть степенью двойки.