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$ – Hagen von Eitzen Apr 2 '15 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$ – Barry Cipra Apr 2 '15 at 22:06
  • $\begingroup$ @ibrhmözbk I guess you want a generalized solution, right? $\endgroup$ – iadvd Apr 3 '15 at 0:26
  • $\begingroup$ iavd, yes I want to find general solution $\endgroup$ – ibrhm özbk Apr 3 '15 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$ – ibrhm özbk Apr 3 '15 at 6:39

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$ – ibrhm özbk Apr 8 '15 at 10:40

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.