Originally Posted by

**redsoxfan325** I hate to say this, but...I'm stuck on an induction proof. I'm trying to prove that $\displaystyle \gcd(F_m,F_n)=F_{\gcd(m,n)}$, where $\displaystyle F_j$ is the $\displaystyle j$th Fibonacci number. I have it reduced to proving that $\displaystyle F_m\,|\,F_{qm}$ for all $\displaystyle m$. I have the rest of the proof.

So I tried proving it with induction.

It's trivial for $\displaystyle m=1$, so I assumed $\displaystyle F_m\,|\,F_{qm}$. Then I tried to prove that $\displaystyle F_{m+1}\,|\,F_{qm+q}$.

Using an identity I know and have proved,

$\displaystyle F_{qm+q}=F_qF_{qm+1}+F_{q-1}F_{qm}=F_qF_{qm+1}+kF_{q-1}F_m$

for some $\displaystyle k\in\mathbb{N}$, but now I'm stuck.

Any hints?