Fibonacci Power!

Number Theory Level 2

How many values of $k$ are there such that $F_k$ is of the form $2^n$ ?

Note that both $k$ and $n$ are non-negative integers.

Also $F_0=0,F_1=1$ and $F_m=F_{m-1}+F_{m-2}$

The answer is 4.

3 solutions

Vishnu C
Jul 1, 2015

I got the result that the greatest Fibonacci number that's a power of 2 is 8 from here . So that leaves $F_1 =F_2 = 1 = 2^ 0;$ $F_3 = 2^ 1$ and $F_6 = 8 = 2^3$ .

That means exactly four powers of 2 in an infinite sequence! Wow!

Can you explain why the greatest power of $2$ is $8$ ?

I was inspired to make this problem when I stumbled across this paper .

Isaac Buckley - 5 years, 11 months ago

I linked it. Didn't you see?

vishnu c - 5 years, 11 months ago

Some parts of the paper went over my head. I've really got to pick up on number theory. But I skimmed through the paper and it seems very interesting.

It's definitely very exciting to say with certainty that only so and so many powers of 2 exist in an infinite sequence!

vishnu c - 5 years, 11 months ago

BeingNotknown Ya
Apr 3, 2019

for $k \leq 6$ , it's easy to check that $k=1,2,3,6$ satisfy the condition.
for $k>6$ , $6|k$ if $F_k$ is of the form $2^n$ .

Let $k=6l$ . We get that $F_l$ and $F_{3l}$ are also of the form $2^n$ . Because $2|F_l$ if and only if $3|l$ , $9|3l$ , so $F_9=34$ is also of the form $2^n$ . Contradict

Kazem Sepehrinia
Jun 29, 2015

I used Carmichael's theorem to find the number of solutions. I would love to see a direct approach for the problem.

Carmichael's theorem: For $n$ greater than $12$ , the $n$ th Fibonacci number $F_n$ has at least one prime divisor that does not divide any earlier Fibonacci number.

Moderator note:

There is an approach that uses a less high-power theorem.

Hint: $F_m \mid F_n \Leftrightarrow m \mid n$

@Calvin Lin Can you please elaborate ?? I couldn't get you!!

Ankit Kumar Jain - 4 years, 3 months ago

Assuming that theorem is true,

(some work required ) Using $F_6 = 8$ , show that if $F_k = 2^n > 8$ , then $k = 6 ^m$ .
Show that $F_{36}$ is not a power of 2. (This can be done without calculating $F_{36}$ ).
Hence, conclude that there is no $F_k = 2^n > 8$ .

Calvin Lin Staff - 4 years, 3 months ago

@Calvin Lin

Although I couldn't reduce $k$ exactly in the form $6^m$ , but something similar to it.

Like clearly as you said $6|k$ . So let $k = 6n$ .

If $2|n \Rightarrow 4|6n \Rightarrow F_4|F_{6n} \Rightarrow F_4 = 2^a$ . But this is not true .

If $3|n \Rightarrow 9|6n \Rightarrow F_9|F_{6n} \Rightarrow F_9 = 2^a$ . But this is not true .

If $5|n \Rightarrow 5|6n \Rightarrow F_5|F_{6n} \Rightarrow F_5 = 2^a$ . But this is not true .

If $p :prime ,p > 6 , p|n \Rightarrow p|6n \Rightarrow F_p|F_{6n} \Rightarrow F_p = 2^a \Rightarrow 6|p$ . But this is not true.

$\therefore n = 1 \Rightarrow \boxed{k = 6}$ is the only possibility.

Please give suggestions and tell me whether I am right or not..!!

Ankit Kumar Jain - 4 years, 3 months ago

@Ankit Kumar Jain – @Calvin Lin

I just got another idea , I could have even directly used the fact that $F_2 , F_3$ are powers to $2$ , and using a similar analysis I could have reached the result.

Am I right enough?

Ankit Kumar Jain - 4 years, 3 months ago

Fibonacci Power!

The answer is 4.

3 solutions

Moderator note:

0 pending reports