Associated Topics || Dr. Math Home || Search Dr. Math

### 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.

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

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/
```
Associated Topics:
College Number Theory
High School Fibonacci Sequence/Golden Ratio
High School Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search