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}$.

  • 3
    $\begingroup$ Why an image for pure text? $\endgroup$ Apr 2, 2015 at 20:51
  • $\begingroup$ It is unclear (to me, at least) what the question is asking for. In particular, what does it mean to say that "no component is not zero"? It looks to me like the example, $a=3$, $b=2$, $p=11$, could be a complete answer. In what sense is it not? $\endgroup$ Apr 2, 2015 at 22:06
  • $\begingroup$ @ibrhmözbk I guess you want a generalized solution, right? $\endgroup$
    – iadvd
    Apr 3, 2015 at 0:26
  • $\begingroup$ iavd, yes I want to find general solution $\endgroup$ Apr 3, 2015 at 6:34
  • $\begingroup$ Barry Cipra-As in example, there is no zero term in a period. {3,2,5,7,1,8,9,6,4,10} .But for example there is one zero term {3,5,8,2,10,1,0,1,1,2} in mod 11. $\endgroup$ Apr 3, 2015 at 6:39

1 Answer 1


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.

  • $\begingroup$ Thanks for your answer. I think this is not true for general fibonacci sequences. for example start with a = 1,b = 3 the formula f( n ) in mod p does not give other term. $\endgroup$ Apr 8, 2015 at 10:40

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .