Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

1 Answer 1

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.