3

Suppose I have a fibonacci sequence 

0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584

Now if I have a modulo 5 fibonacci sequence,it will look like

0 1 1 2 3 0 3 3 1 4 0 4 4 3 2 0 2 2 4 1 0 1 1 2 3 0 3 3 1

If I have modulo 7 fibonacci sequence it will look like

0 1 1 2 3 5 1 6 0 6 6 5 4 2 6 1 0 1 1 2 3 5 1 6 0 6 6 5 4 2 6

Now,we notice that the pattern repeats in the modular fibonacci sequence. I want to know what is the point at which the pattern starts repeating.I mean what is the relationship of the repetiton-start-position with the modular number like 5,7,11,etc.

Please keep it as simple as possible.I have to use this concept in an algorithm

EDIT On some research I found this as the answer,but it involves lot of maths which I cannot understand.Can someone please decode it and give me a direct expression

Naveen
  • 31

1 Answers1

3

You are referring about the Pisano period. There is no way to compute this besides direct computation. However, you can a period which may be, but is not necessarily, the minimal period.

Denoting the period of the Fibonacci sequence modulo $p$ as $\pi(p)$, with a prime $p\neq 5$, we can find that $F_{p-\left(\frac{p}{5}\right)}\equiv 0\,(\bmod\, p)$ and $F_p \equiv \left(\frac{p}{5}\right)(\bmod\, p)$, where $\left(\frac{p}{5}\right)$ is a Legendre symbol.

In other words,

  • If $p \equiv \pm 1 \,(\bmod \,5)$ then we have that $F_{p-1}\equiv 0\,(\bmod\, p)$ and $F_p \equiv 1\,(\bmod\, p)$, so that $p-1$ marks the start of the first repetition of the sequence. Therefore, $\pi(p) \mid p - 1$
  • Otherwise, if $p \equiv \pm 2 \,(\bmod \,5)$ then $F_{p+1}\equiv 0\,(\bmod\, p)$ and $F_{p}\equiv p-1\,(\bmod\, p)$. From this, we can find that $F_{2p+1} \equiv 1\,(\bmod\, p)$ and $F_{2p+2}\equiv 0\,(\bmod\, p)$. Therefore, $F_{2p+3}\equiv 1\,(\bmod\, p)$ and we have a periodicity of $2p + 2$ - that is, $\pi(p) \mid 2(p+1)$.

So $p-1$ and $2(p+1)$ may serve as effective periodicities for each case, respectively.

Here is a good paper with more basic exposition.

Sajjan Singh
  • 131