# Proving that $n|m\implies f_n|f_m$

Question: Let $m,n\in\mathbb{N}$, prove that if $n|m$, $F_n|F_m$.

I've tried to use induction, but I don't really know where to start since there's $2$ numbers: $n$ and $m\ \dots$ I did induction before with just $1$ number, like proving $1+2+\cdots+n=\frac{n(n+1)}{2}$, that's only dealing with one number $n$, but with this I have no clue how to do it.

Can anyone give me a little hint on how to start, I don't want you to do whole problem for me but can I have some hint so I know where to start?

Thanks for the help!

• Is $F_n$ the $n^{th}$ Fibonacci number? You should use only $F$ or $f$ if they are the same thing. – Git Gud May 1 '13 at 11:19
• From Lemma# 4 of fq.math.ca/Scanned/4-3/halton.pdf, $(F_m,F_n)=F_{(m,n)}$ – lab bhattacharjee May 1 '13 at 11:53

## 2 Answers

Hint: Try to prove that $f_{n+m}=f_{n-1}\ f_m+f_n\ f_{m+1}$.

Then, let $m=n\times k$ for some $k\in \mathbb{N}$.

Now, prove that $f_m$ is divisible $f_n$ by induction on $k$.

• I think I got it, appreciated for help! – Charles G May 1 '13 at 11:38

You can prove the desired result without induction using Binet's formula, $$F_n = \frac{\varphi^n - \psi^n}{\sqrt{5}}$$ where $\varphi$ and $\psi$ are the roots of $x^2 + x + 1$, and the factoring identity $$a^n - b^n = (a - b)(a^{n-1} + a^{n-2}b + a^{n-3}b^2 + \cdots + ab^{n-2} + b^{n-1}).$$

• Does this mean that: $$ψ = \frac{1 - \sqrt{5}}{2} = φ - \frac{\sqrt{20}}{2}$$ – Feeds Sep 24 '17 at 4:20
• @user477343 You should be able to answer that yourself. – Maurice P Sep 24 '17 at 15:50