<s>[INST] Fibonacci numbers divisible by $9$ The $n$th Fibonacci number $F_n$ is defined as follows,$$F_1=F_2=1\mbox{ and } F_{n+2}=F_{n+1}+F_{n}\mbox{ for } n\geq 1$$
I want to know how many of the first $1000$ Fibonacci numbers are divisible by $9$ ? Is it possible to classify all Fibonacci numbers which are divisible by $9$ ?
I have searched in Google and found in an article that says every $12$th Fibonacci number is divisible by $9$ but no proof is given. Are these the only such numbers ? Any idea for the soloution would be helpful.
 [/INST] First, let's prove if $n$ divisible by $m$, then $F_n$ is also divisible by $F_m$.
To prove it we need formula $$\Large{F_{n+k} = F_{k+1} \cdot F_n + F_k \cdot F_{n-1}} \; (1) $$
Therefore, $F_{2n} = F_{n+1} F_n + F_n F_{n-1}$ is divisible by $F_n$, and $F_{3n} = F_{2n + n} = F_{2n+1} F_n + F_{2n} F_{n-1}$ is divisible by $F_n$, and so on.
Using induction method, let's assume $F_{k \cdot n}$ is divisible by $F_n$, therefore, $$\Large{F_{(k+1)n} = F_{kn +n} = F_{n+1} F_{kn} + F_n F_{kn-1}} \; (2) $$ is also divisible by $F_n$.
Now, we need to find all Fibonacci numbers which are divisible by 9. The first Fibonacci number which is divisible by 9 is $F_{12}=144$.

Therefore, $F_{12n}$ is divisible by 9.

Now, let's prove, that there is no other Fibonacci number which is divisible by 9.
$$ \begin{array}{|c|c|}
\hline
F_{1} \equiv 1 \; (mod \; 9) & F_{13} \equiv 8 \; (mod \; 9) \\ 
F_{2} \equiv 1 \; (mod \; 9) & F_{14} \equiv 8 \; (mod \; 9) \\ 
F_{3} \equiv 2 \; (mod \; 9) & F_{15} \equiv 7 \; (mod \; 9) \\ 
F_{4} \equiv 3 \; (mod \; 9) & F_{16} \equiv 6 \; (mod \; 9) \\ 
F_{5} \equiv 5 \; (mod \; 9) & F_{17} \equiv 4 \; (mod \; 9) \\ 
F_{6} \equiv 8 \; (mod \; 9) & F_{18} \equiv 1 \; (mod \; 9) \\ 
F_{7} \equiv 4 \; (mod \; 9) & F_{19} \equiv 5 \; (mod \; 9) \\ 
F_{8} \equiv 3 \; (mod \; 9) & F_{20} \equiv 6 \; (mod \; 9) \\ 
F_{9} \equiv 7 \; (mod \; 9) & F_{21} \equiv 2 \; (mod \; 9) \\ 
F_{10} \equiv 1 \; (mod \; 9) & F_{22} \equiv 8 \; (mod \; 9) \\ 
F_{11} \equiv 8 \; (mod \; 9) & F_{23} \equiv 1 \; (mod \; 9) \\ 
F_{12} \equiv 0 \; (mod \; 9) & F_{24} \equiv 0 \; (mod \; 9) \\ \hline
\end{array}$$
It will continue in the same sequence. Which means only $F_{12n}$ is divisible by 9.

Prove (1) using induction, also. 

</s>