Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
Let $f(0)=a$ and $f(1)=b$ be the first two terms of a Fibonacci sequence. We know that this sequence is periodic in $\mod{p}$, where $p$ is a prime number, and the period of the sequence is $p-1$. I want to find the sequences such that no term is zero. How do I choose $a$ and $b$.
For example, if the first two terms are $3$ and $2$, then the Fibonacci sequence is $\{3,2,5,7,1,8,9,6,4,10\}$ in $\mod{11}$.
As a pedestrian answer, first try $a=0$ and $b=1$. If you find that a certain element is missing from the sequence then apply an affine transformation so that $0$ is missing.
To write down something more mathematical, let's assume that $p\equiv 1\text{ or }4\pmod{5}$, so that $$\gamma_{\pm} = (1\pm 5^{1/2})/2\pmod{p}$$ are well defined and distinct. Then the Fibonacci sequence is given by $$f(n) = A{\gamma_+}^n + B{\gamma_-}^n$$ for some $A,B$ which depend on your starting values. This sequence avoids the value $0$ iff $A(\gamma_+/\gamma_-)^n$ avoids the value $-B$. The obvious solution is to take $A=0$ and $B\neq 0$ or vice versa, which corresponds to the choice $a=x, b=\gamma_\pm x$ for any $x\neq 0$ and either choice of sign. Whether or not these are all the solutions depends on whether $$\gamma_+/\gamma_- = -(3+5^{1/2})/2$$ is a primitive root modulo $p$.
If $p\equiv 2\text{ or }3\pmod{5}$ then $\gamma_\pm$ are elements not of $\mathbf{F}_p$ but rather of $\mathbf{F}_{p^2}$, and the coefficients $A,B\in\mathbf{F}_{p^2}$ must be chosen with the additional property that $A+B,A\gamma_++B\gamma_-\in\mathbf{F}_p$. Thus the trivial solutions are ruled out, and there are no solutions at all if $\gamma_+/\gamma_-$ is a generator of $\mathbf{F}_{p^2}^\times$, which I suppose is the case often enough.
