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$

1 Answer 1

Reset to default
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$
1
  • $\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
    Commented Jan 26, 2016 at 18:44

You must log in to answer this question.

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