# Divisibility and the Fibonacci Sequence Proof [duplicate]

Let $$F_n$$ be the Fibonacci sequence ($$F_1=1, F_2=1, F_3=2, \ldots F_n$$ such that $$F_n = F_{n-1} + F_{n-2}$$). Show that $$F_n$$ divides $$F_{rn}$$ for all $$r,n \ge 1$$.

I'm not sure how to show this rigorously. I feel that eventually the terms repeat and so $$F_{nr} = qF_n$$, where $$q$$ is an integer.

image

(I attached the problem in an image since I used LaTex with my intuition.) I thought about using induction but got nowhere and am completely stuck. How would I start and what would I need to show? This is for an introductory number theory class.

## marked as duplicate by Brahadeesh, ancientmathematician, ArsenBerk, Shailesh, Tom-TomNov 16 '18 at 8:44

• Forgot something? – Hagen von Eitzen Oct 5 '17 at 22:12
• Sorry, I fixed it. – Dominated Convergence Theorem Oct 5 '17 at 22:17
• The Fibonacci sequence: $F_n = F_{n-1} + F_{n-2}$ Now substitute $F_{n-1} = F_{n-2} + F_{n-3}$ into the previous. Keep doing it. Can you find a pattern? Derive a new formula for the sequence such that $F_n = F_k\times \text {Something} + \text {Something else}$ and then show that if $k$ divides $n, F_k$ is a factor of both terms. – Doug M Oct 5 '17 at 22:24
• I found the equality F_n = F_{k+1} F{n-k} + F_k F{n-k-1}. The problem is if I decompose F_{k+1}, I get two terms, so I can't factor F_k from the equality stated. – Dominated Convergence Theorem Oct 5 '17 at 22:27
• @DominatedConvergenceTheorem Please do not replace the question details with a "thanks" post. That qualifies as defacement and should never be done; doing so can get you in trouble. – Brahadeesh Oct 4 '18 at 16:45

Suppose that $F_n\equiv 0 \bmod k$, and $F_{n+1} \equiv c \bmod k$. Then of course immediately $F_{n+2} \equiv 0{+}c$ $\equiv c \bmod k$ and thus $F_{n+i} \equiv cF_i \bmod k$ and $F_{2n+i} \equiv c^2F_i \bmod k$ etc.
In particular $F_{rn} \equiv c^{r-1} F_n$ $\equiv c^{r-1}{\cdot\,} 0$ $\equiv 0 \bmod k$.
In the specific case of this question, set $k=F_n$.