How to find a Fibonacci number that is divisible by $x$?

I'm looking for an algorithm that is better than just checking every number in the Fib Sequence for divisibility.

Example: Find the first Fib number that is divisible by $x=223321$, with no remainders.

Answer: The $15720$th Fib Number, which is a $3285$ digit number.

I'm currently checking every digit, that gets to be too much too fast and makes it impossible to check larger numbers, like $x=1024240$.

Appreciate the read.

Answer

Note first that it may help to factorise your large number if it is not prime. Here there is a fairly obvious factor $7$ ($203=210-7$) and you get $223321= 7 \times 31903$.

Now look at the Fibonacci Sequence modulo $7$, which goes $1,1,2,3,5,1,6,0,6,6,5,4,2,6,1,0,1,1 \dots$.

It is then easy to show that every eighth term is divisible by $7$. You will have to do less work if you know the theorem that if $F_1=F_2=1; F_{n+1}=F_n+F_{n-1}$ then $F_n\mid F_{kn}$.

Then you can use the same method with the second factor, which turns out to be $61 \times 523$. Then you know that the position in the sequence is divisible by $8$ and two other numbers - take the least common multiple to find the index.

So this gives lcm of $8, 15, 524$ which is $15720$

---

$1024240=2^4\times 5 \times 7 \times 31 \times 59$ so the index can be found a great deal more quickly using the factorisation.

So $16$ is a factor every $12^{th}$ number, $5$ gives $5$, $7$ gives $8$, $31$ gives $30$ and $59$ gives $58$.

So we need the least common multiple of $12,5,8,30,58$ - this makes it the $3480^{th}$ element of the sequence

---

Lemma $11$ of this paper shows that an odd prime divides one of $F_{p-1}, F_p, F_{p+1}$ and tells you which, and the paper gives information on how to compute the index when the prime factorisation is known.

To summarise $5\mid F_5$, and the option is $p-1$ where $p$ is congruent to $\pm 1 \bmod 5$, $p+1$ otherwise. But this need not be the least index for a prime, and doesn't deal with prime powers.