Last Four Digits of the Fibonacci Numbers

Date: 05/06/2001 at 22:13:24
From: Sam
Subject: Fibonacci numbers

How can I show that there is a number ending with four zeros in the 
Fibonacci sequence?

Also, how do I prove that the Fibonacci sequence has a cycle for the 
last 4 digits with a cycle length of 15,000?

Date: 05/07/2001 at 15:51:58
From: Doctor Floor
Subject: Re: Fibonacci numbers

Hi Sam, thanks for writing.

Usually we take the Fibonacci numbers to be F_1 = 1, F_2 = 1, F_3 = 2, 
etc. But this time we want to include F_0 = 0.

For your first question we will not look at the Fibonacci numbers 
themselves, but at the residues after division by 10,000. Those 
numbers, which we will call F*_n, represent the final four digits. 
They start like this:

     0, 1, 1, 2, 3, ...

but they never exceed 10,000.

Two consecutive entries of this sequence fix the rest:

   * forward by the usual formula F*_n = F*_{n-1} + F*_{n-2} and 
     subtracting 10,000 if necessary,

   * backward by F*_n = F*_{n+2} - F*_{n+1} and the addition of 10,000
     if necessary.

There are only 10,000^2 = 100,000,000 possible pairs of consecutive 
entries, and thus, going along the sequence F*, there must be two 
distinct pairs of consecutive entries (F*_t, F*_{t+1}) and {F*_u, 
F*_{u+1}) (with t and u not equal) that are equal. From these pairs we 
can go back to (F*_0, F*_1) and a pair (F*_v, F*_{v+1}) for v > 0 that 
are equal as well. But that means that F_v, the real v-th Fibonacci 
number, must be divisible by 10,000.

That proves your first question.

The number 10,000 in the above can be replaced by any other number. So 
for each number m there is an n > 0 such that m is a divisor of F_n.

This is a very special property of Fibonacci numbers. It is (for 
instance) not true for the very related Lucas numbers, which have the 
same recurrence formula but start with 1, 3, ... There is no Lucas 
number that ends with a 0, which can be seen if we make the sequence 
of residues of Lucas numbers after division by 10:

     1, 3, 4, 7, 1, 8, 9, 7, 6, 3, 9, 2, 1, 3, ...

and we see that the pattern repeats, while the 0 (and the 5) have not 
appeared.


From the above it is easy to see that all sequences of residues after 
division by a certain n are periodical. From this we see that F(n) is 
a divisor of F(n*m). 

Another way that this can be shown depends more on computations; see 
from the Dr. Math archives

   Primes in Fibonacci
   http://mathforum.org/dr.math/problems/white07.11.99.html   

This can be helpful to find the answer of your second question. We 
know that the prime factorization of 10,000 is 2^4 * 5^4. We look for 
the smallest n such that F_n is divisible by 10,000.

Very quickly we find that F_3 = 2, so we have to look only to F_n for 
n equal to a multiple of 3. With F_5 = 5, and F_6 = 8 this quickly 
leads to F_30 = 832,040, which is the smallest Fibonacci number 
divisible by 2^3*5. So now we only look for F_n with n being a 
multiple of 30, etc.

Good luck! If you need more help, just write back.

Best regards,
- Doctor Floor, The Math Forum
  http://mathforum.org/dr.math/