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 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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994-2013 The Math Forum