# Fibonacci-like sequences mod $p$ where $a_{n+1}$ only really depends on $a_n$.

Consider a prime $$p$$ and a sequence $$(a_n)_{n\ge 0}$$ in $$\mathbb{F}_p$$ satisfying $$a_{n+2}=a_{n+1}+a_n$$ for all $$n\ge 0$$.

Now, assume that each element of the sequence only really depends on the previous one. That is, assume there exists a function $$f:\mathbb{F}_p\to\mathbb{F}_p$$ such that $$a_{n+1}=f(a_n)$$ for all $$n\ge 0$$.

If $$p\not\in\{2,5\}$$ and $$5$$ is a quadratic residue mod $$p$$ there are the obvious sequences $$\left(c\left[\frac12+\frac12\sqrt5\right]^n\right)_{n\ge 0}\quad\text{and}\quad\left(c\left[\frac12-\frac12\sqrt5\right]^n\right)_{n\ge 0}$$ for $$c\in\mathbb{F}_p$$ any constant, but are there any others?

## Computational results by @Servaes

Let's call two Fibonacci-like sequences modulo $$p$$ equivalent if they can be turned into each other through shifting and multiplication by units, then any sequence where each element is a function of the previous and and which is not equivalent to $$(0)_{n\ge 0},\quad (c^n)_{n\ge 0}$$ where $$c^2=c+1$$, is called strange.

@Servaes has shown through computation that the first few primes for which strange sequences exist are $$199, 211, 233, 281, 421, 461, 521, 557, 859, 911.$$

## Own work

For any prime $$p$$ let $$\pi(p)$$ be the Pisano period mod $$p$$ (so this is not the prime counting function)

Claim: Let $$p$$ be a prime, $$(a_n)_{n\ge 0}$$ a strange sequence. Then it has period $$\pi(p)$$.

Proof: Let $$A=\{a_n:n\ge 0\}$$ be the set of attained values and $$f:A\to A$$ the function which makes this sequence strange, in the sense that $$a_{n+1}=f(a_n)$$ for all $$n\ge 0$$. Clearly, $$f$$ is a bijection.

It is easily proved that, for all $$a\in A$$ and $$n\in\mathbb{Z}$$, $$f^n(a)=F_{n-1}a+F_nf(a).$$ Let $$m$$ be the period of $$(a_n)_{n\ge 0}$$, then clearly $$m$$ is the smallest positive integer $$n$$ for which $$f^n=\operatorname{id}_A$$. Thus, for all $$a\in A$$, $$(1-F_{m-1})a=F_mf(a)$$ If $$F_m\neq 0$$ it follows that $$f(a)=F_m^{-1}(1-F_{m-1})a$$ and the sequence is equivalent to $$\left(c^n\right)_{n\ge 0}$$ where $$c=F_m^{-1}(1-F_{m-1})$$ satisfies $$c^2=c+1$$. This contradicts our assumption that the sequence is strange, so $$F_m=0$$.

Since the sequence is not the null sequence, we may take $$a\in A$$ non-zero and conclude that $$F_{m-1}=1$$. It follows that $$\pi(p)\mid m$$. Since $$f^{\pi(p)}(a)=F_{\pi(p)-1}a+F_{\pi(p)}f(a)=F_{-1}a+F_0F(a)=a,$$ the opposite division relation holds as well and we are done.

EDIT: I asked a slightly more general version of this question on Mathoverflow and linked to this question, but forgot to link the Mathoverflow question here.

• For $p=5$ the sequence $(2,1,3,4,2,1,\ldots)$ works. And of course the zero sequence works for any $p$. There are no other sequences (up to shifting) for $p\leq5$. Sep 15 '20 at 22:33
• Also, except the zero sequence, no sequence can contain a $0$. Nor can it have $a_{n+1}=a_n$ for any $n$. Moreover, if $(a_n)_{n\geq0}$ is such a sequence the so is $(ca_n)_{n\geq0}$ for any constant $c$. So without loss of generality $a_0=1$. This leaves $p-2$ initial values for $a_1$, for each $p$. Sep 15 '20 at 22:40
• Some simple python code shows that the first primes for which there are not either $0$ or $2$ such sequences, up to multiplication by constants and shifting, are: $$5,\ 199,\ 211,\ 233,\ 281,\ 421,\ 461,\ 521,\ 557,\ 859,\ 911.$$ Sep 15 '20 at 23:09
• I'm still cleaning up the proof, but I believe that the period of any sequence not of the 'standard' types must be the Pisano period mod p. Sep 15 '20 at 23:25
• Quite surprisingly, it seems that the number of values for $a_1$ that yields such a sequence is either $1+\left(\tfrac{5}{p}\right)$, except for the primes I just listed, in which case the number of values for $a_1$ is huge! Sep 15 '20 at 23:30