Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
9  
The proof is easy: just calculate the fibonacci numbers mod 9. –  Chris Eagle Dec 6 '12 at 10:24
2  
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". –  Hendrik Jan Dec 6 '12 at 10:36
1  
add comment

2 Answers 2

up vote 11 down vote accepted

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.

share|improve this answer
add comment

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$

share|improve this answer
    
I think you accidentally exchanged the sub-indices, obviously $m>n\iff F_m>F_n$. –  tohecz Dec 6 '12 at 10:45
    
@tohecz, thanks for your observation –  lab bhattacharjee 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$ –  pritam Dec 6 '12 at 11:00
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.