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.

Let $\{ F_n\}$ be the sequence of numbers defined by $F_1=1=F_2;\, F_{n+1}=F_n+F_{n-1}$ for $n \geq 2$. Let $f_n$ be the remainder left when $F_n$ is divided by $5$. Then $f_{2000}$ equals

(A) $0$ $~~~~~~~~~~~~~~~~$ (B) $1$ $~~~~~~~~~~~~~~~~$ (C) $2$$~~~~~~~~~~~~~~~~$ (D) $3$

I found that $F(1)=1$, $F(2)=1$, $F(3)=2$, $F(4)=3$, $F(5)=5$, $F(6)=8$, $F(7)=13$, $F(8)=21$, $F(9)=34$, and $F(10)=55$. But I need a systematic pattern to find $F_n$.

share|improve this question
5  
Look at the remainders of the fibonacci sequence upon division by $5$ (aka "modulo $5$"). Then you will see that it repeats. (It must: any finite recursion relation solution defined on a finite set must eventually repeat.) –  anon Mar 28 '13 at 13:45

5 Answers 5

up vote 3 down vote accepted

Now the pattern for the remainder is, $f_{1}=1$, $f_{2}={1}$, $f_{3}={2}$, $f_{4}={3}$ now we have $f_{5}=0$. So this is our first zero. If you proceed in this manner you will see that $f_{10}=0$ and $f_{15}=0$ and so on. So, $f_{2000}=0$.

share|improve this answer
2  
This is a valid observation, but not a rigorous proof. Note that $F_6\equiv 3$, $F_7\equiv 3$ etc, so the remainders mod $5$ do not repeat every $5$ numbers. (In fact, the cycle length is $20$). –  azimut Mar 28 '13 at 17:30

$\rm{\bf Hint}\ \ \ mod\ 5\!:\,\ F_{k}\!\equiv\color{#0A0}0\:\Rightarrow\:F_{k+5}\!\equiv\color{#C00}0\ \ \ by\ \ \ \begin{array}{|c|c|c|c|c|c|} \hline \rm k&\rm k\!+\!1 &\rm k\!+\!2 &\rm k\!+\!3 &\rm k\!+\!4 &\rm k\!+\!5\\ \hline \color{#0A0}0&\rm n &\rm n &\rm 2n &\rm 3n &\rm \color{#C00}0 \\\hline\end{array}$

share|improve this answer
    
A nice observation! –  barto Apr 9 at 11:58

$$F_n=F_{n-1}+F_{n-2}=F_{n-2}+F_{n-3}+F_{n-2}=2F_{n-2}+F_{n-1}$$ $$=2(F_{n-3}+F_{n-4})+F_{n-3}=3F_{n-3}+2F_{n-4}$$

$$=3(F_{n-4}+F_{n-5})+2F_{n-4}=5F_{n-4}+3F_{n-5}$$

$$\text{ So,} F_n\equiv 3F_{n-5}\pmod 5 $$

As $F_1=F_2=1\implies F_0=F_2-F_1=0\equiv0\pmod 5$

$\implies 5\mid F_n$ if $5\mid n$


Alternatively, from Lemma#$5$ of this , $F_n\mid F_m \iff n\mid m\text{ or } n=2$ for $m\ge n\ge 1$

We find $F_2=F_1=1,F_3=2,F_4=3, F_5=5$

So, $F_5\mid F_m \iff 5\mid m$ for $m\ge1$

share|improve this answer
    
Wish I could thank somebody for pinpointing the mistake. –  lab bhattacharjee Mar 29 '13 at 16:43
    
Thank you so much, sir! Your explanations are always complete and self-explaining. –  Sush Apr 9 at 13:43

Hint:

Show by induction that $F_n \equiv 2n3^n\mod 5$.

share|improve this answer

Since we have all these nice answers here, I thought I'd provide the obvious solution: \begin{align}f_{2000}=F_{2000}\bmod 5=&42246963333923048787067256023414827825798528402506\\ &81098010280137314308584370130707224123599639141511\\ &08844608753890960360764019471164359602927198331259\\ &87373262535558026069915859152294924539049987222567\\ &95316982874482472992263901833716778060607011615497\\ &88671987985831146887087626459736908672288402365442\\ &22952433479644801395153495629720876526560695298064\\ &99841977448720155612802665404554171717881930324025\\ &204312082516817125\bmod 5=0\end{align}

(It's a lot easier to use $5\mid F_5\mid F_{5\cdot200}$ though.)

share|improve this answer

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.