Numbers in the Fibonacci Sequence

Date: 07/19/2001 at 17:29:55
From: Dinu Razvan
Subject: Number Theory

How can I show that there is a number in the Fibonacci sequence that 
ends in 999999999999 ? 

For what numbers n is there a number in the Fibonacci sequence that 
ends in n of 9 ?

Date: 07/20/2001 at 11:24:49
From: Doctor Rob
Subject: Re: Number Theory

Thanks for writing to Ask Dr. Math, Dinu.

This hinges on the period of the Fibonacci numbers when reduced
modulo powers of 10.

First, you need to know that the Fibonacci numbers are periodic with
period 3 when reduced modulo 2, and period 20 when reduced modulo 5.
Thus the period modulo 10 is the LCM of 3 and 20, or 60.

Next, you want to see what happens modulo 2^2, 2^3, 2^4, ... The 
period doubles with each extra power of 2, so modulo 2^n it is
3*2^(n-1).  

Next, you want to see what happens modulo 5^2, 5^3, 5^4,... The period 
is multiplied by 5 for each extra power of 5, so for modulo 5^n it is 
4*5^n. Then the period modulo 10^n = 2^n * 5^n is

   LCM[3*2^(n-1), 4*5^n] = LCM[4,15*10^(n-1)].

That means that the period modulo 10^2 is 300, and mod 10^n for
n >= 3, it is 15*10^(n-1).

Now you can find that F(-2) = -1 by using the Fibonacci recurrence
backward. Then F(-2) = -1 (mod 10^n) for all n. Then by using the
periodicity, you can figure out that

   F(60-2) = F(58) = -1 (mod 10),
   F(300-2) = F(298) = -1 (mod 10^2),
   F(15*10^[n-1]-2) = -1 (mod 10^n) for all n >= 3.

For example, F[1499998] must end in 999999.

I leave it to you to fill in the proofs of the statements above.

- Doctor Rob, The Math Forum
  http://mathforum.com/dr.math/