Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

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/   
    
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

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/