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.

• The proof is easy: just calculate the fibonacci numbers mod 9. Dec 6 '12 at 10:24
• And, in the same way as the comment above you can calculate the Fibonacci numbers modulo 9 for your answer. The sequence (mod 9) will repeat in 24 steps. Google "fibonacci modulo". Dec 6 '12 at 10:36
• math.stackexchange.com/questions/60340/… Dec 6 '12 at 10:44

Looking at the Fibonacci numbers $\bmod\ 9$ yields $$\color{#C00000}{0,1,}1,2,3,5,8,4,3,7,1,8,\color{#0000FF}{0,8,}\dots\tag{1}$$ Since the blue terms are the negative of the red terms, we get $$F_{n+12}\equiv-F_n\pmod{9}\tag{2}$$ Since the only Fibonacci number in the first $12$ that is $0\bmod9$ is $F_0$, we get $$F_n\equiv0\pmod{9}\Longleftrightarrow n\equiv0\pmod{12}\tag{3}$$ Therefore, $84$ of the first $1000$ Fibonacci numbers are divisible by $9$ if you start with $F_0$, but if you start with $F_1$, only $83$ of the first $1000$ are.

We know from here ,here or here, $$F_m\mid F_n \iff m\mid n$$ or $$m=2$$

now $$F_{12}=144$$ so, $$144\mid F_{12k}$$ where $$k$$ is natural number.

As $$F_{12k}\equiv 0\pmod 9$$ and if $$F_{12k-1}\equiv a\pmod 9, (a,9)=1$$ as $$(F_m,F_{m+1})=1$$

So, $$F_{12k+1}\equiv (a+0)\pmod 9\equiv a\cdot F_1$$ $$F_{12k+2}\equiv (a+a)\pmod 9\equiv a\cdot F_2 ,$$ $$F_{12k+3}\equiv (2a+a)\pmod 9\equiv a\cdot F_3$$ and so on upto $$F_{12k+11}\equiv a\cdot F_{11}$$

again, $$F_{12k-2}=F_{12k}-F_{12k-1}\equiv 0-a\pmod 9\equiv -a\cdot F_1,$$ $$F_{12k-3}\equiv -a-a\pmod 9\equiv -a\cdot F_2$$ and so on upto $$F_{12k-11}\equiv -a\cdot F_{10}$$

As observed by Hendrik Jan, the period is $$24$$,

so $$9\mid F_n\iff 12\mid n$$

Hence, the numbers required Fibonacci number is $$\lfloor \frac{1000}{12}\rfloor=83$$

• I think you accidentally exchanged the sub-indices, obviously $m>n\iff F_m>F_n$.
– yo'
Dec 6 '12 at 10:45
• @tohecz, thanks for your observation Dec 6 '12 at 10:47
• @labbhattacharjee: Putting $m=12$ in your formula we have $12|n$ iff $144|F_n$, so this implies if $12|n$ then $9|F_n$. But as I want to count all the fibonacci numbers divisible by $9$, I need something like this $9|F_n$ iff $x|n$ Dec 6 '12 at 11:00

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.
• In the first formula, what if $n=0$? Other than that, great answer $(+1)$ May 22 '18 at 11:26