# Prove: the intersection of Fibonacci sequence and Mersenne sequence is just $\{1,3\}$

$$\frac{{{\varphi ^n} - {{(1 - \varphi )}^n}}}{{\sqrt 5 }} = {2^m} - 1 .$$ Here $\varphi = \frac{{1 + \sqrt 5 }}{2}$ . This integer equation has no solution for $n>3$ and $m>2$. How to prove?

-

We need to find when $F_n+1$ is a power of 2. Almost every value of $n$ can be eliminated by considering the Pisano period. In particular, we can deduce that:

• $F_n+1 \equiv 0 \pmod {16}$ if and only if $n \equiv 22 \pmod {24}$ and
• $F_n+1 \equiv 0 \pmod 9$ if $n \equiv 22 \pmod {24}$.

This leaves the few small cases already listed.

-
You mean mod 8 instead of mod 9, don't you? – Hans Lundmark Jan 7 '11 at 11:16
I mean (mod 9) -- since powers of 2 are not divisible by 9, we can deduce that if F_n+1 is a power of 2, then it is less than 16 (which leaves a few small cases to check). – Douglas S. Stones Jan 7 '11 at 11:21
I have known that $F_n=4k-1$ iff n=6a+4. – a boy Jan 7 '11 at 11:47
The first few values of F_n+1 are 2, 2, 3, 4, 6, 9 and 14. The remaining values 22, 35,... are all more than 16 (and if they happen to be divisible by 16, they are also divisible by 9, and therefore are not powers of 2). – Douglas S. Stones Jan 7 '11 at 11:53
Thank you!you are right! – a boy Jan 7 '11 at 12:05