25
$\begingroup$

Are there infinitely many Fibonacci numbers that are also powers of 2? If not, which is the largest?

$\endgroup$
35
$\begingroup$

Fibonacci numbers have just about the greatest divisibility rule you could expect. Fibonacci numbers share common divisors exactly when their corresponding indices share common divisors, $\gcd(F[m],F[n])$ = $F_{\gcd(m,n)}$.

This result means that the Fibonacci index of any power of $2$ greater than $8$ must be divisible by $6$ as $F_6 = 8$ and this means that the index of power of $2$ Fibonacci number greater that $8$ must be a power of 6 and therefore must be divisible by $F_{36}$.

However $F_{36}$ is also divisible by $F_{9}$ since $9$ divides $36$ and given that $F_9 = 34, F_{36}$ is therefore divisible by $34$ and cannot be a power of $2$.

Since any candidate powers of $2$ greater than $8$ must be divisible by $34$ there can be no Fibonacci numbers greater than $8$ which are powers of $2$.

$\endgroup$
  • $\begingroup$ I got that the index must be divisible by 6, but didn't understand why it must be a power of 6. $\endgroup$ – Anant May 15 '14 at 12:55
  • 3
    $\begingroup$ I don't think it does; it just has to be divisible by 6 and have prime factorisation only containing 2s and 3s. But the same proof (using $F_4$ as well as $F_9$) seems to work. $\endgroup$ – Christopher May 15 '14 at 13:23
  • 1
    $\begingroup$ I'm a bit confused right now. Why is is gcd in the topmost equation? Shouldn't it be something like just cd? $\endgroup$ – Max Ried May 15 '14 at 15:53
13
$\begingroup$

As far as I can tell, as a corollary of Carmichael's theorem, it follows that no Fibonacci numbers other than $1$, $2$ and $8$ can be powers of $2$. Thus, $8$ is the largest.

$\endgroup$
10
$\begingroup$

There are three, and the biggest is 8.

$\endgroup$
  • 11
    $\begingroup$ For posterity, please avoid link-only answers and also replicate the information here. Websites go down and information on them changes over time. If quoting from a source, also provide attribution. $\endgroup$ – Kyle Falconer May 15 '14 at 20:47
  • $\begingroup$ There are 4. Note that one is repeated. So they are 1, 1, 2, 8. $\endgroup$ – Confuse Jul 16 '15 at 15:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.