4
$\begingroup$

I wonder is there more effective algorithm than brute-force-search to find the first Fibonacci number with given remainder $~~r~~$ modulo given integer $~~m~~$.

$$ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, ...$$

If $~~m=6~~$ and $r=0$ then $F_{12} = 144$ is the first Fibonacci number such that $$~~F_{n} = 0 \pmod 6$$

If $~~m=7~~$ and $r=3$ then $F_{4} = 3$ is the first Fibonacci number such that $$~~F_{n} = 3 \pmod 7$$

I also wonder how to check if such Fibonacci number exists because if $m=8$ and $r=4$ then no Fibonacci number satisfies congruence $~~F_{n} = 4 \pmod 8$

Thanks in advance for any ideas.

$\endgroup$
0
$\begingroup$

I don't know of a more effective algorithm than brute force search, but let's consider a question like "is there any Fibonacci number with $F_n = 4 \pmod 8$". If you write out the Fibonacci numbers modulo 8 you get the sequence

$1, 1, 2, 3, 5, 0, 5, 5, 2, 7, 1, 0, 1, 1, \ldots$

where each entry is the sum of the previous two, reduced modulo 8. Once $1, 1$ reoccurs the sequence repeats. So you can see from this that $F_n = 4 \pmod 8$ and $F_n = 6 \pmod 8$ never occur. The point here is that once you see $1, 1$ again you can stop computing.

$\endgroup$
  • $\begingroup$ An interesting case is that if $5$ is a square modulo $m$, for odd $m$ not divisible by $5$ then if $r$ has a solution, then $5r^2+4$ is a square modulo $m$. This condition is not (likely) sufficient, though. $\endgroup$ – Thomas Andrews Jan 26 '16 at 18:44

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.