jasperE3 wrote: The Fibonacci sequence $f_n$ is defined by $f_1=f_2=1$ and $f_{n+2}=f_{n+1}+f_n$ for $n\in\mathbb N$. (a) Show that $f_{1005}$ is divisible by $10$. (b) Show that $f_{1005}$ is not divisible by $100$. solution of a I will prove that every $f_{15k}$ is divisible by 10. First of all I'll prove that every $f_{3k}$ is divisible by $2$ (by induction). My base case is $f_3=2$ which is divisible by $2.$ Now let $f_{3m}\equiv 0 (mod 2)$. Let, $f_{3m-1}\equiv k (mod 2)$ then $f_{3m+1}\equiv k (mod 2)$ $f_{3m+2}\equiv k(mod 2)$ $f_{3m+3} \equiv 2k\equiv 0(mod 2)$ Similarly, by taking $f_5=5$ as base case you( or we) can prove that $f_{5k}\equiv 0(mod 5).$ So, $f_{15k}\equiv 0(mod 10)$ As, $15|1005,$ $10$ divides $f_{1005}.$