Fibonacci sequence modulo 10

Suppose $F_n\equiv 0$ and $F_{n+1}\equiv x$ , and x coprime to 10, then we get the following terms by calculating (mod 10):

So we observe that the first term after $F_n$ that is 0 (mod 10) is $F_{n+15}$ . Since $7x$ is also coprime to $10$ , we could repeat the same the argument by induction, so that 0 occurs exactly every 15th term. The initial condition is $F_0=0$ and $F_1=1$ , so right from the start this pattern emerges, so that $10|F_n \Leftrightarrow 15|n$ , from which it follows that k=15.

If we write down the first few terms we see that:

• $F_{0} \equiv 0$
• $F_{15} \equiv 0$
• $F_{30} \equiv 0$
• $F_{45} \equiv 0$
• $F_{60} \equiv 0$

And at this point the series repeats, therefore the pattern will continue, and since 15 is the also the first positive $n$ for which $F_{n} \equiv 0$ , then the answer is $15$ .

For hypothesis we have $F_{n}\equiv 0\; (mod\; 10)$ . Let's see how it works for next terms.

$F_{n+1}=F_n+F_{n-1}\equiv F_{n-1}\;(mod\;10)$

$F_{n+2}=F_{n+1}+F_n\equiv F_{n-1}\;(mod\;10)$

$F_{n+3}=F_{n+2}+F_{n+1}\equiv 2F_{n-1}\;(mod\;10)$

It seems that $F_{n+k}\equiv F_k\cdot F_{n-1}\;(mod\;10)$ ... Let's prove it by strong induction on $k$ .

Base case: we have just calculated $F_n$ and $F_{n+1}$ ; thesis holds for both of them.

Induction step:

$F_{n+k+1}=F_{n+k}+F_{n+k-1}$ for definition

$\equiv F_{k}\cdot F_{n-1}+F_{k-1}\cdot F_{n-1}$ for inductive hypothesis

$=(F_k+F_{k-1})\cdot F_{n-1}$

$=F_{k+1}\cdot F_{n-1}$ for definition.

Therefore $F_{n+k}\equiv F_k\cdot F_{n-1}\;(mod\;10)$ for strong induction on $k$ .

In general it's NOT true that $ab\equiv 0 \;(mod\; m) \Rightarrow a\equiv 0 \; (mod\; m) \lor b\equiv 0 \; (mod\; m)$ . But, since the problem's thesis must holds for all $n$ satisfying $F_n\equiv 0 \; (mod\; 10)$ , it has to be $F_k\equiv 0 \; (mod\; 10)$ in order to have $F_{n+k}\equiv 0 \; (mod \; 10)$ .

With simple calculations we find out that $min\{k\in \mathbb{N}:\; F_k\equiv 0 \; (mod\; 10)\}=\boxed{15}$ .

By writing this sequence down modulo 10 we can see that we start with 1, 1 and eventually get to 1, 1 again. This means it cycles (only two previous numbers influence the next number). We can also see that between every pair of neighbouring 0s there are 14 numbers therefore the answer.