Divisibility and the Fibonacci sequence While studying the Fibonacci sequence I encountered this problem in the handout, and I can not understand how to do it.

Show that if the Fibonacci sequence has a term divisible by a natural number $m$, then there are infinitely many such terms.

 A: The duplication identity for the Fibonacci numbers states:
$$
    F_{2m} = F_m \left( F_m + 2 F_{m-1} \right)
$$
Hence, for some $k \in \mathbb{N}$, if $F_m$ is divisible by $k$, every element of the sequence $F_{2m}, F_{4m}, \ldots, F_{2^r m}, \ldots$ is also  divisible by $k$.
A: Hint: Consider the sequence modulo $m$. This sequence is (immediately) periodic.

I'm assuming you know what modular arithmetic is.
Claim: The sequence modulo $m$ is immediately periodic.
Proof: 


*

*Every term of the sequence is uniquely defined by the 2 terms preceding it. Hence, given any pair of consecutive terms, we know what the rest of the terms are.

*Consider pair of consecutive terms taken modulo $m$. There are $m \times m$ possibilities for the pairs. Since this is finite, and we have infinitely many pairs, there must be (at least) 1 pair that repeats (at least once). From the first observation, this shows that the sequence is (eventually) periodic. [The period is a factor of the difference of the indices of the terms.]

*In fact, if we know what 2 consecutive terms are, then we know what the previous term is, and hence every term that comes before it. Thus, the sequence is immediately periodic.
A: I thought so:$$\fbox{Lemma 1: $a\mid b\Longleftrightarrow u_a\mid u_b$, in Fibonacci sequence}$$We have $m\mid u_n$ and $\exists a\in\mathbb{N}$ with $a\geq n$ such that $n\mid a$ therefore, by Lemma 1: $u_n\mid u_a$; and if $n\mid a\Longrightarrow n\mid ak\;\;\;\forall k\in \mathbb{N}$ soon $$u_n\mid u_{ak}\;\;\forall k\in\mathbb{N}$$ as $m\mid u_n$ and $u_n\mid u_{ak}\;\;\forall k\in\mathbb{N}$ then $m\mid u_{ak}\;\;\forall k\in\mathbb{N}$ Since $k$ can take any natural $u_{ak}$ has infinite values.​​$\;\;\;\;\Box$$$$$Correct?
A: Since
$$
F_n=\frac{\phi^n-(-1/\phi)^n}{\sqrt5}
$$
we also have
$$
F_{mn}=\frac{\phi^{mn}-(-1/\phi)^{mn}}{\sqrt5}
$$
Therefore,
$$
\begin{align}
\frac{F_{mn}}{F_n}
&=\frac{\phi^{mn}-(-1/\phi)^{mn}}{\phi^n-(-1/\phi)^n}\\
&=\sum_{k=1}^m\phi^{(m-k)n}(-1/\phi)^{(k-1)n}\\
&=\sum_{k=1}^{\lfloor m/2\rfloor}\left(\phi^{(m-k)n}(-1/\phi)^{(k-1)n}+\phi^{(k-1)n}(-1/\phi)^{(m-k)n}\right)\\
&\hphantom{=}+(-1)^{(m-1)n/2}[m\text{ is odd}]\\
&=\sum_{k=1}^{\lfloor m/2\rfloor}(-1)^{(k-1)n}\left(\phi^{(m-2k+1)n}+(-1/\phi)^{(m-2k+1)n}\right)\\
&\hphantom{=}+(-1)^{(m-1)n/2}[m\text{ is odd}]\\
&=\sum_{k=1}^{\lfloor m/2\rfloor}(-1)^{(k-1)n}L_{(m-2k+1)n}\\
&\hphantom{=}+(-1)^{(m-1)n/2}[m\text{ is odd}]\\
\end{align}
$$
where $L_n$ are Lucas Numbers and $[\dots]$ are Iverson Brackets.
The important thing is that $\dfrac{F_{mn}}{F_n}\in\mathbb{Z}$.
