# Let $F_n$ be the $n$-th Fibonacci number. Prove or disprove: $5 | F_{5k}$ for all positive integers $k$

Given the following proof:

Let $F_n$ be the $n$-th Fibonacci number. Prove or disprove: $5 | F_{5k}$ for all positive integers $k$.

I am confused exactly where to start. The Fibonacci numbers are defined recursively correct? So wouldn't this be something that I can prove with strong induction?

Well, $F_5=5$ and $5\mid5$, right?!

Now, suppose that $5\mid F_{5k}$. Then\begin{align}F_{5(k+1)}&=F_{5k+5}\\&=F_{5k+4}+F_{5k+3}\\&=F_{5k+3}+F_{5k+2}+F_{5k+2}+F_{5k+1}\\&=F_{5k+3}+2F_{5k+2}+F_{5k+1}\\&=F_{5k+2}+F_{5k+1}+2F_{5k+1}+2F_{5k}+F_{5k+1}\\&=3F_{5k}+5F_{5k+1}.\end{align}Since $5\mid F_{5k}$, it follows from this that $5\mid F_{5(k+1)}$.

• Exactly what I was trying to do thank you! – APorter1031 Nov 15 '17 at 23:13
• You stopped at 3F5k+5F5k+1 because it is of the form k + k+1, correct? – APorter1031 Nov 15 '17 at 23:49
• @APorter1031 No, not at all. It's because $5F_{5k+1}$ is trivially a multiple of $5$ and $3F_{5k}$ is a multiple of $5$ since I am assuming that $F_{5k}$ is a multiple of $5$. My proof is a proof by induction of the assertion$$(\forall k\in\mathbb{N}):5\mid F_{5k}.$$ – José Carlos Santos Nov 15 '17 at 23:52
• ahh, thank you for the clarification! – APorter1031 Nov 15 '17 at 23:52

Just using the recurrence $F_{n+1}=F_n+F_{n-1}$ few times, you can get $$F_{5n+5}=5F_{5n+1}+3F_{5n}$$ You can use this identity to prove your claim by induction.

If we take $F_1=F_2=1$, then we certainly have that $5|F_5=5$. Let's look at the Fibonacci numbers, reduced modulo $5$:

$F_1\equiv 1\\ F_2\equiv 1\\ F_3\equiv 2\\ F_4\equiv 3\\ F_5\equiv 0\\ F_6\equiv 3\\ F_7\equiv 3\\ F_8\equiv 1\\ F_9\equiv 4\equiv -1\\ F_{10}\equiv 0\\ F_{11}\equiv -1\\ F_{12}\equiv -1\\ F_{13}\equiv -2\\ F_{14}\equiv -3\\ F_{15}\equiv 0\\ F_{16}\equiv -3\\ F_{17}\equiv -3\\ F_{18}\equiv -1\\ F_{19}\equiv -4\equiv 1\\ F_{20}\equiv 0\\$

After this, the pattern begins to repeat, and it appears that $F_{n+20}\equiv -F_{n+10}\equiv F_n$ for all $n$. This, together with $F_5\equiv F_{10}\equiv 0\pmod 5$ is sufficient to establish your claim.

You don't have to define the Fibbonacci sequence recursively

You could say:

$F_n = \frac{\phi^n + \phi'^n}{\phi - \phi'}$

where $\phi = \frac {1 + \sqrt 5}{2}$ and $\phi' = \frac {1 - \sqrt 5}{2}$

$F_{5k} = \frac{\phi^{5k} + \phi'^{5k}}{\phi - \phi'} = \frac{\phi^{5} + \phi'^{5}}{\phi - \phi'} (\phi^{5k-5} + \phi^{5k-10}\phi' + \cdots \phi'^{5k-1}) = F_5(\phi^{5k-5} + \phi^{5k-10}\phi' + \cdots \phi'^{5k-1})$

and $F_5 = 5$

More generally $k|n \implies F_k | F_n$

Modulo $5$ the Fibonacci sequence becomes $$0,1,1,2,3,0,3,3,1,4,0,4,4,3,2,0,2,2,4,1,0,1, ...$$ and from this point on repeats periodically. So we see that for indexes $5k$ we have $F_{5k}\equiv0\bmod5$.

The characteristic polynomial of the sequence $\{F_n\}_{n\geq 0}$ is the minimal polynomial of $\varphi$ over $\mathbb{Q}$, namely $x^2-x-1$. It follows that the characteristic polynomial of the sequence $\{F_{5n}\}_{n\geq 0}$ is the minimal polynomial of $\varphi^5$, namely $x^2-11x-1$, and $$F_{5k+10} = 11 F_{5k+5} + F_{5k}.$$ Since both $F_0$ and $F_5$ are multiples of $5$, the previous recurrence implies that $5\mid F_{5k}$ for any $k\in\mathbb{N}$. Actually, we can say much more: due to this version of Hensel's lifting lemma, $$\nu_5(F_n) = \nu_5(n)$$ which can be proved through the following identity, too: $$\begin{eqnarray*} F_{5k} &=& F_k (\varphi^{4k}+\varphi^{3k}\overline{\varphi}^k+\varphi^{2k}\overline{\varphi}^{2k}+\varphi^k\overline{\varphi}^{3k}+\overline{\varphi}^{4k})\\&=&F_k\left(25 F_k^4+25F_k^2+5\right)\\&=&5F_k\underbrace{(5F_k^4+5F_k^2+1)}_{\not\equiv 0\pmod{5}}\end{eqnarray*}$$ implying $\nu_5(F_{5k})=1+\nu_5(F_k)$.

Let \begin{eqnarray*} A= \begin{bmatrix} 0 &1 \\1 &1 \\ \end{bmatrix} . \end{eqnarray*} Then
\begin{eqnarray*} A^n= \begin{bmatrix} F_{n-1} &F_n \\F_n &F_{n+1} \\ \end{bmatrix} \end{eqnarray*} and \begin{eqnarray*} A^5= \begin{bmatrix} 3 &5 \\5 &8 \\ \end{bmatrix} . \end{eqnarray*}

In particular \begin{eqnarray*} A^{5n}= \begin{bmatrix} F_{5n-1} &F_{5n} \\F_{5n} &F_{5n+1} \\ \end{bmatrix} . \end{eqnarray*} \begin{eqnarray*} A^{5n+5}= \begin{bmatrix} F_{5n+4} &F_{5n+5} \\F_{5n+5} &F_{5n+6} \\ \end{bmatrix} = \begin{bmatrix} . &3F_{5n}+5F_{5n+1} \\. &. \\ \end{bmatrix} . \end{eqnarray*} and thus the result follows by induction.