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.
Best 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.