# Diophantine equation: fermat numbers and fibonacci numbers

My question is how to find all solutions $(m,n)\in\mathbb N^2$ for $F_n=f_m$, where $F_n=2^{2^n}+1$ and $f_m$ is the $m$th fibonacci number: $f_0=0$, $f_1=1$ and $f_n+f_{n+1}=f_{n+2}$ for each $n\in\mathbb N$.

Maybe this topic can give some inspiration for proving that there are no solutions for $m>5$: Fibonacci[n]-1 is always composite for n>6. why?

-

$f_4 = 2^{2^0} + 1$ and $f_5 = 2^{2^1} + 1$, but I suspect that there is no $m > 5$ such that $f_m - 1$ is a power of $2$, let alone $2$ to a power of $2$. A search of $m \le 100000$ yields none.

EDIT: It appears that the least $m>2$ such that $f_m - 1$ is divisible by $2^j$ is $3 \times 2^{j-1} - 1$ for $j \ge 2$. Since those $f_m - 1$ are also divisible by $3$ for $j \ge 4$ (in fact $f_m \equiv 1 \mod 3$ for $m \equiv -1 \mod 8$), they are not powers of $2$.

EDIT: Let $m(j) = 3 \times 2^{j-1} - 1$. I claim that for $j \ge 2$ \eqalign{f_{m(j)} &\equiv 1 + 2^j \mod 2^{j+1} \cr f_{m(j)+1} &\equiv 0 \mod 2^{j+1}\cr} It is true for $j=2$: $m(2) = 5$, $f_5 = 5 = 1+2^2$ and $f_6 = 8 = 2^3$. Now $m(j+1) = 2 m(j) + 1$, so using the identity $f_{2m+1} = f_{m+1}^2 + f_{m}^2$ $$f_{m(j+1)} = f_{m(j)+1}^2 + f_{m(j)}^2 \equiv 1 + 2^{j+1} \mod 2^{j+2}$$ because $f_{m(j)+1}^2$ is divisible by $2^{2(j+1)}$ and therefore by $2^{j+2}$, while if $x \equiv 1 + 2^j \mod 2^{j+1}$ with $j \ge 2$, $x^2 \equiv 1 + 2^{j+1} \mod 2^{j+2}$ Similarly, using the identity $f_{2m+2} = (2 f_m + f_{m+1}) f_{m+1}$, we get $$f_{m(j+1)+1} = (2 f_{m(j)} + f_{m(j)+1}) f_{m(j)+1} \equiv 0 \mod 2^{j+2}$$ because the first factor is even and the second is divisible by $2^{j+1}$. By induction, the claim is proved.

One consequence of this is that $f_k \mod 2^j$ is periodic with period $m(j)+1$.

Next, I claim that if $f_k \equiv 1 \mod 2^j$ (with $j\ge 2$) then $k \equiv 1, 2$ or $-1 \mod m(j)+1$. Again we induct on $j$. It is true for $j=2$. Suppose it's true for $j$. If $f_k \equiv 1 \mod 2^{j+1}$ then $f_k \equiv 1 \mod 2^j$ so by the induction hypothesis $k \equiv 1, 2$ or $-1 \mod m(j)+1$, and thus (since $m(j+1)+1 = 2 (m(j)+1)$) $k \equiv 1, 2, m(j), m(j)+2, m(j)+3$ or $-1 \mod m(j+1)+1$. But by the above we know that $f_{m(j)} \equiv 1 + 2^j \mod 2^{j+1}$, and also both $f_{m(j)+2} = f_{m(j)} + f_{m(j)+1}$ and $f_{m(j)+3} = f_{m(j)+1} + f_{m(j)+2} \equiv 1 + 2^j \mod 2^{j+1}$. By the periodicity, $f_k \equiv 1 + 2^j \mod 2^{j+1}$ for $k \equiv m(j), m(j)+2$ or $m(j)+3 \mod m(j+1)+1$.
So that leaves only $1, 2$ and $-1 \mod m(j+1)+1$. This proves the claim.

In particular, there are no $k$ with $2 < k < m(j)$ such that $f_k \equiv 1 \mod 2^j$. And since $f_{m(j)} > m(j) > 2^j + 1$, this shows that $2^j + 1$ is not a Fibonacci number for $j > 2$.

-
Another great answer by Robert :) –  mick Oct 30 '12 at 19:40
A first question: (probably it won't be the last...) How can you see that $f_k\mod2^j$ is periodic with period $m(j)+1$? Of course it is periodic, but I don't know why it is with this period. –  barto Oct 30 '12 at 22:35
I think I almost know why. Since $f_{m(j)}\equiv1\pmod{2^j}$ and $f_{m(j)}\equiv0\pmod{2^j}$ we have that $f_{m(j)+x+1}\equiv f_x\pmod{2^j}$, and so the period is a divisor of $m(j)+1$. –  barto Oct 30 '12 at 22:51
The fact that the period is not smaller then $m(j)+1$ follows out of the fact that there are no $k$ with $2< k< m(j)$ such that $f_k\equiv1\pmod{2^j}$, right? If yes, then I finally understand your proof completely :) It is indeed awesome. –  barto Oct 31 '12 at 11:13