What is the period of Fibonacci mod 10?

Question

In previous questions we found that the last digit of a Fibonacci sequence repeated after a certain number of terms.

http://answers.yahoo.com/question/index?qid=20080829050836AAnUufc

http://answers.yahoo.com/question/index;_ylt=AshI9nWYp_dn1nLC6FNFheTsy6IX;_ylv=3?qid=20080828062849AAmxgrr

The numbers of terms before a repetition depended on the starting two numbers. lavalamp3773 found that it repeated after 12 terms when the starting numbers are 1 and 3. manjyome found this and several other starting pairs give a period of 12. lavalamp3773 found starting pairs with a period of 1 and another with a period of 3. Falcor84 also found a sequence with period 3. farful found a sequence with a period of 60.

http://answers.yahoo.com/question/index;_ylt=AqC2gG.KvLl2DiwGkU.xk1bsy6IX;_ylv=3?qid=20080827140147AA99Gxw

Let FP(i,j) be a function of the starting numbers i, j of a Fibonacci sequence where FP(i,j) is the period of the sequence mod 10.

i and j are the integers from 0 to 9.

Can anyone make a formula using i and j that gives FP(i,j), or can anyone give a verbal description?

Answer 1

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.

Answer 2

See

http://en.wikipedia.org/wiki/Pisano_peri...

for the answer and

http://en.wikipedia.org/wiki/Fibonacci_n...

for another general discussion modulo n.

The FP(i,j) subquestion sounds interesting ;-) I have only looked at this on paper and it seems there are possible periods of 60, 20, 12, 4, 3, and 1. I don't know any general rule from which it would follow which the particular initial condition will fall in, though...

Added:

Observation 1: The possible periods mod n are all divisors of the period when beginning with 0, 1, are not necessarily different and summed together, they give n^2.

Example: 60, 20, 12, 4, 3 and 1 are all divisors of 60 and 60 + 20 + 12 + 4 + 3 + 1 = 100 = 10^2.

Observation 2: When a and b are relatively prime, then the possible periods mod n = ab are all the LCMs (are "multiples" enough?) of all possible periods when taking mod a and when taking mod b.

Example:

2^2 = 3 + 1 [FP2(0,1) = FP2(1,0) = FP2(1,1) = 3, FP2(0,0) = 1]

5^2 = 20 + 4 + 1

10^2 = 3*20 + 3*4 + 3*1 + 1*20 + 1*4 + 1*1 = 60 + 12 + 3 + 20 + 4 + 1, see above.

The way I found this is ugly so I won't tell it here. Having these two results, it's fairly easy to find that for FP(i, j) in mod 10 (FP10(i, j) according to the above notation), we need the same in mod 2 and mod 5 and take the LCM of these two. Example:

for FP10(2,6), we need FP2(2, 6) = FP2(0, 0) = 1 and FP5(2, 6) = FP5(2, 1) = 4. Therefore, FP10(2, 6) = gcd(1, 4) = 4. Indeed, i=2 and j=6 give the sequence 2, 6, 8, 4, 2, 6, 8, 4, ... with period 4.

Conclusion:

FP(i, j) = k*l, where

k = 1 if both i and j are even, 3 otherwise

l = 1 if both i and j are divisible by 5

l = 4 if (i mod 5, j mod 5) is an element of the set {(1,3), (2,1), (3,4), (4,2)}

l = 20 otherwise

It's still quite complicated, but explicit anyhow. I don't think I will come up with something better unless focusing heavily on the topic. I will let this to more experienced users ;-)

Note:

> I notice a permutation in the fourth line of your conclusion:

> (1,3), (3,4), (4,2), (2,1); (1, 3, 4, 2).

Well, it is, but I am quite sure this is a random coincidence. This is one of the possible periods mod 5. There are two other: (0) and something with length 20. (This is expressed by the funny formula 5^2 = 20 + 4 + 1 above.) The last one is surely not a permutation.

I think it will be best to reformulate the last lines a bit:

Given i and j, we take (a, b) = (i mod 2, j mod 2) and (c, d) = (i mod 5, j mod 5). These two tuples determine the periods of the sequence taken mod 2 or mod 5, respectively.

In the former case, there are two possible periods: (0) and (1, 1, 0). If both a and b are 0, we have the first one of length 1, in any other case (10, 01, or 11), we have the second one with length 3.

In the case of mod 5, there are three possibilities: a period (0) of length 1, period (1, 3, 4, 2) with of 4 and one period of length 20, containing all the other pairs of numbers from 0 to 4. So, we must find our pair (c,d) among these to determine the other ancillary subperiod. c=d=0 gives the first case, pairs 13, 34, 42, or 21 the second and any other the last one.

As math_kp stated, it is fairly easy to find that we need to find a least common multiplier of these two numbers (which is in every case here the same as just multiplying them) to get the final period mod 10.

I don't know whether you exactly needed such a clarification, but it might be helpful for anyone ;-)