The smallest Fibonacci number that can be divided by $2^m$

Question

How can i calculate the smallest Fibonacci number that can be divided by $2^m$ (a big number). I tried computing with a dynamic algorithm but it reaches a point where my RAM simply can't carry on. Any ideas?

Answer 1

Your should look at this summary The Fibonacci Sequence Modulo m by Marc Renault.
It contains a lot of information about divisibility properties of Fibonacci sequences.

According to section D. "Facts on the rank of $F \pmod m$" on above summary,

The smallest Fibonacci number that can be divided by $2^m$ is $F_{\alpha(2^m)}$ where $$\alpha(2) = 3,\quad\alpha(2^2) = 6\quad\text{ and }\quad \alpha(2^m) = 6\cdot 2^{m-3} \quad\text{ for } m \ge 3$$

Look at there for related results and references.

Answer 2

The Fibonacci numbers, mod $2^m$, are periodic, with period less than $2^{m+1}$. Further, the period begins with $0,1$. For a proof, see here.

Hence, once they begin to repeat, you will get a Fibonacci number with $2^m$ as divisor. You can do all computations modulo $2^m$, which hopefully won't overtax your RAM.

Answer 3

You can do all of your calculations mod $2^n$ to start. For example, if you wanted to find the smallest n such that $2^m | F_n$ with m = 2 you can keep track of the remainder of $F_i$ and $F_{i+1}$ mod 4. This would proceed like so:

$$F_1 = 1 \,mod\, 4$$ $$F_2 = 1 \,mod\, 4$$ $$F_3 = 2 \,mod\, 4$$ $$F_4 = 3 \,mod\, 4$$ $$F_5 = 1 \,mod\, 4$$ $$F_6 = 0 \,mod\, 4$$

And you could then conclude that $F_6$ is the smallest Fibonacci divisible by $2^2$ and then use an alternate method to calculate the value of $F_6$. The advantage of this method is that you only need to keep track of two numbers of m bits which represent the last two remainders. Adding these two remainders is very straightforward as well and should not burden your computer too much.