5
$\begingroup$

We know that Fibonacci sequences are periodic in mod $m$. For example, for $p\equiv \pm 1 \pmod 5$ and $p\equiv \pm 2 \pmod 5$ the periods for Fibonacci sequences modulo $p$ divide $p-1$ and $2p+2$ respectively. I want to find the number of zeros in the Fibonacci sequences modulo $p$ which have maximal period for these special cases. For example, if we take $p=11$ then the period is $10$ and the sequence is $\{0,1,1,2,3,5,8,2,10,1\}$ and there is only one zero. For $p=19$ the period is $18$ and the sequence is $\{0,1,1,2,3,5,8,13,2,15,17,13,11,5,16,2,18,1\}$ and there is only one zero. But, for $p=41$ the period is $40$ and the sequence is $\{0,1,1,2,3,5,8,13,21,34,14,7,21,28,8,36,3,39,1,40,0,40,40,39,38,36,33,28,20,7,27,34,20,13,33,5,38,2,40,1\}$ there are two zeros. My question is that: "Can we give an implicit formula, which count the number of zeros in a sequence for given maximal periods?"

$\endgroup$
1
$\begingroup$

New edit:I forgot the $\text{ord}_n(F_{k+1}) $ part actually tells you how many 0's there are before the end of the period. Thus here is new, edited answer:

Find $k$ where $k$ is the smallest positive integer such that $n\mid F_k$ ($n$ being the index of the highest Fibonacci Number ($F_n$). Now, the amout of 0's is $\lfloor {p \over k} \rfloor + 1$, where $\lfloor x \rfloor$ is the floor rounding function. If you start the sequence from $F_0$ otherwise if it is $F_1$ it would just be $\lfloor {n \over k} \rfloor$ obviously.

However, this doesn't tell us much does it? It just says that the distance between $0$'s in $F_n \mod p$ is always the same.

There may be a few special cases, but one of the most interesting cases is when $p = F_k$. That means that when you are modding to a Fibonacci number, the amount of $0$'s in the OTHER Fibonacci sequence is just $\lfloor {n \over k} \rfloor$. (Note that $k$ has a different context in this setting.)

Thus there is no easy way to calculate them without finding that initial $0$, however we know that since $\pi (p) < p^2$ The maximum "tries" to find it is going to be $p^2$.

Finally, in the entire context of my answer, $p$ does not necessarily prime.

$\endgroup$
  • 2
    $\begingroup$ The pattern explicitly does not repeat after every zero, even for primes - see the example of the sequence mod 41 given in the OP itself. (Because the Fibonacci recurrence is order 2, canonically the period can be of size $\approx p^2$ rather than just size $p$.) $\endgroup$ – Steven Stadnicki Jun 21 '14 at 2:58
  • $\begingroup$ My mistake, it as at least the lower limit then. $\endgroup$ – Dane Bouchie Jun 21 '14 at 15:59
  • $\begingroup$ Aha! The multiplicative order actually tells you how many 0's are inside the period. And actually the period cannot be around $p^2$ because if $p$ is prime, then it must be $p-1$ or $2p+2$, Now adjusted my answer. $\endgroup$ – Dane Bouchie Jun 22 '14 at 19:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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