Last Four Digits of the Fibonacci NumbersDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/