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?"
-
$\begingroup$ See math.stackexchange.com/q/790390/115115, with the link webspace.ship.edu/msrenault/fibonacci/fib.htm given there discussing exactly this topic. $\endgroup$– Lutz LehmannCommented May 14, 2014 at 15:22
-
$\begingroup$ Check out my edited answer. $\endgroup$– Dane BouchieCommented Jun 22, 2014 at 19:25
1 Answer
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.
-
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$ Commented Jun 21, 2014 at 2:58
-
$\begingroup$ My mistake, it as at least the lower limit then. $\endgroup$ Commented Jun 21, 2014 at 15:59
-
1$\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$ Commented Jun 22, 2014 at 19:23