Are there infinitely many Fibonacci numbers that are also powers of 2? If not, which is the largest?
3 Answers
$\begingroup$
$\endgroup$
4
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$.
-
$\begingroup$ I got that the index must be divisible by 6, but didn't understand why it must be a power of 6. $\endgroup$– AnantMay 15, 2014 at 12:55
-
4$\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$ May 15, 2014 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$– bot47May 15, 2014 at 15:53
-
$\begingroup$ Not sure if it helps anyone, was just hovering over this question. @Christopher I think in the case above, $n$ must be divisible by 36. Substitute $m$ = 36, $F_n$ = $2^k$. Then in the gcd equation, LHS is a power of 2 (>8 because $F_{6}$ is a common factor). RHS is $F(6*gcd(6, n/6))$. By using same gcd equation (if $d | n$ then $F_{d} | F_{n}$), we know $F_{gcd(6, n/6)}$ must divide LHS which is a power of 2. This means $6 | gcd(6, n/6) $, which means n/6 is a multiple of 6, or in other words $36 | n$ $\endgroup$ Sep 8 at 13:53
$\begingroup$
$\endgroup$
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.
2
-
12$\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$ May 15, 2014 at 20:47
-
$\begingroup$ There are 4. Note that one is repeated. So they are 1, 1, 2, 8. $\endgroup$– ConfuseJul 16, 2015 at 15:02