About the percentage of the mutiples of a prime $p$ in Fibonacci sequence Suppose that a sequence $\{f_n\}$ is defined as $$f_1=f_2=1, f_{n+2}=f_{n+1}+f_n\ \ (n\ge1).$$
Supposing that for a prime number $p$ and a natural number $N$,$$F_p(N)=\{\ n\ |\ n \in\mathbb N,\ n\le N, \ f_n\equiv0 \ (mod \ p)\}$$ and that the number of natural numbers included in $F_p(N)$ is defined as $\#F_p(N)$.
Then, my first question is to prove that for any $p$, there exists $$\lim_{N\to\infty}\frac{\#F_p(N)}{N}$$
and that the limiting value is not $0$.
In addition to this, my second question is to evaluate the following two.$$\lim_{N\to\infty}\frac{\#F_{17}(N)}{N}, \lim_{N\to\infty}\frac{\#F_{19}(N)}{N}$$
I've tried to prove this, but I'm facing difficulty. I need your help. Tnank you.
 A: Let's begin the Fibonacci sequence at index $0$ with $f_0 = 0$, that makes many things more convenient.
The fundamental equality I shall exploit in the following is
$$f_{n+k} = f_{k+1}\cdot f_n + f_k\cdot f_{n-1}\tag{1}$$
for all $n,\,k$ (if $n = 0$, the identity uses also $f_{-1} = 1$; the Fibonacci sequence can be extended to negative indices, you get $f_{-k} = (-1)^{k+1}f_k$).
$(1)$ can easily be proved by induction on $k$, for $k = 0$, it reduces to $f_n = 1\cdot f_n + 0\cdot f_{n-1}$, and for $k = 1$ to $f_{n+1} = f_2\cdot f_n + f_1\cdot f_{n-1} = f_n + f_{n-1}$, which is just the defining recurrence. Then, knowing $(1)$ to hold for $k \leqslant m$, we find
$$\begin{align}f_{n+(m+1)} &= f_{n+m} + f_{n+(m-1)}\\
&= \bigl(f_{m+1}\cdot f_n + f_m\cdot f_{n-1}\bigr) + \bigl(f_m\cdot f_n + f_{m-1}\cdot f_{n-1}\bigr)\\
&= (f_{m+1} + f_m)\cdot f_n + (f_m + f_{m-1})\cdot f_{n-1}\\
&= f_{m+2}\cdot f_n + f_{m+1}\cdot f_{n-1}
\end{align}$$
and the last line is $(1)$ for $k = m+1$.
From $(1)$, we can easily deduce
Lemma: Let $n \in \mathbb{N}$. For all $q\in \mathbb{N}$, $f_{q\cdot n}$ is a multiple of $f_n$.
For $q = 1$ (and $q = 0$), that is immediate. Having our base case, we conclude with
$$f_{(q+1)\cdot n} = f_{n + q\cdot n} = f_{q\cdot n + 1}\cdot f_n + f_{q\cdot n}\cdot f_{n-1}$$
that, since $f_n$ divides $f_{q\cdot n}$ by the induction hypothesis, and it divides $f_n$ trivially, we also have the desired $f_n \mid f_{(q+1)\cdot n}$.
Another very important result we obtain from $(1)$ is the
Proposition: For all $k,\, n \in \mathbb{N}$,
$$\gcd (f_n,f_k) = f_{\gcd (n,\,k)}.\tag{2}$$
For the proof, note first that $(2)$ is true if $n = 0$ or $k = 0$, since $\gcd (a,0) = a$. Next, we treat the special case $n = k\pm 1$. The induction start is $\gcd (f_1,\, f_0) = \gcd (1,\,0) = 1$, and then we have $\gcd (f_{n+1},\,f_n) = \gcd (f_n + f_{n-1},\,f_n) = \gcd (f_{n-1},\,f_n) = 1$ by the induction hypothesis.
For general $0 < k < n$, write $n = q\cdot k + r$ with $0 \leqslant r < k$ to obtain
$$f_n = f_{r+1}\cdot f_{q\cdot k} + f_r\cdot f_{q\cdot k - 1}.$$
By the above lemma, $f_{q\cdot k}$ is a multiple of $f_k$, hence $\gcd (f_n,\, f_k) = \gcd (f_r\cdot f_{q\cdot k - 1},\, f_k)$. But by the special case proved above, $\gcd (f_{q\cdot k-1},\, f_{q\cdot k}) = 1$, and since $f_k$ is a divisor of $f_{q\cdot k}$, we have $\gcd (f_{q\cdot k-1},\,f_k) = 1$ and hence
$$\gcd (f_n,\, f_k) = \gcd (f_r,\, f_k).$$
Continuing with the Euclidean algorithm yields the proposition.
For the aims of your question, we wrap it up in the
Theorem: Let $p$ a prime, and $n_p = \min \{n > 0 : f_n \equiv 0 \pmod{p}\}$. Then $$f_k \equiv 0 \pmod{p} \iff k \equiv 0 \pmod{n_p}$$
and hence
$$F_p(N) = \{ k\cdot n_p : 1 \leqslant k,\, k\cdot n_p \leqslant N\},\quad \#F_p(N) = \left\lfloor\frac{N}{n_p}\right\rfloor.$$
Consequently, $$\lim_{N\to\infty}\frac{\#F_p(N)}{N} = \frac{1}{n_p}.$$
What remains is to show that $n_p$ exists for all primes $p$. For $p = 2$, we find $n_2 = 3$ by inspection. For odd primes $p$, we use Binet's formula
$$f_n = \frac{\varphi^n - \psi^n}{\varphi - \psi},$$
where $$\varphi = \frac{1 + \sqrt{5}}{2};\quad \psi = \frac{1-\sqrt{5}}{2} = 1 - \varphi = - \frac{1}{\varphi}.$$
Then binomial expansion of $\varphi^n$ and $\psi^n$ together with $\varphi - \psi = \sqrt{5}$ yields
$$\begin{align}
2^p f_p &= \frac{1}{\sqrt{5}}\left(\sum_{k=0}^p \binom{p}{k}\sqrt{5}^k - \sum_{k=0}^p \binom{p}{k}(-1)^k\sqrt{5}^k \right)\\
&= \frac{2}{\sqrt{5}}\sum_{m=0}^{\frac{p-1}{2}} \binom{p}{2m+1}\sqrt{5}^{2m+1}\\
&= 2\sum_{m=0}^{\frac{p-1}{2}} \binom{p}{2m+1}5^m.
\end{align}$$
Using the fact that $\binom{p}{k} \equiv 0 \pmod{p}$ for $0 < k < p$ and Fermat's theorem $a^{p-1} \equiv 1 \pmod{p}$ if $a \not\equiv 0 \pmod{p}$, we obtain
$$\begin{align}
f_p \equiv 2^{p-1}f_p \equiv 5^{\frac{p-1}{2}} \pmod{p}.
\end{align}$$
This shows $n_5 = 5$ (which we could also have found by inspection ;), so in the following, we assume $p \neq 5$.
The analogous computation for $f_{p+1}$ yields
$$2^pf_{p+1} = \sum_{m=0}^{\frac{p-1}{2}} \binom{p+1}{2m+1}5^m$$
and since $\binom{p+1}{k} \equiv 0 \pmod{p}$ for $1 < k < p$, we obtain
$$2 f_{p+1} \equiv 2^p f_{p+1} \equiv \binom{p+1}{1} + \binom{p+1}{p}5^{\frac{p-1}{2}} \equiv 1 + 5^{\frac{p-1}{2}}\pmod{p}.$$
By Fermat's theorem, $\lambda_p = 5^{\frac{p-1}{2}}$ satisfies $\lambda_p^2 \equiv 1 \pmod{p}$, so $\lambda_p \equiv \pm 1 \pmod{p}$.
If $\lambda_p \equiv -1 \pmod{p}$, then $f_{p+1} \equiv 0 \pmod{p}$, and if $\lambda_p \equiv 1 \pmod{p}$, then $f_{p+1} \equiv \frac{1+\lambda_p}{2} \equiv 1 \equiv \lambda_p \equiv f_p \pmod{p}$, whence $f_{p-1} = f_{p+1} - f_p \equiv 0 \pmod{p}$.
So: $n_2 = 3;\, n_5 = 5$, and for $p \neq 2,\,5$, we have $n_p \mid p+1$ if $\lambda_p \equiv -1 \pmod{p}$ and $n_p \mid p-1$ if $\lambda_p \equiv 1 \pmod{p}$.
Note: $\lambda_p \equiv 1 \pmod{p}$ if and only if $p \equiv \pm 1 \pmod{5}$.
We find $n_{17} = 9$, and $n_{19} = 18$.
