# Math Help - Proof of Divisibilty propery of Fibonaccia numbers.

1. ## Proof of Divisibilty propery of Fibonaccia numbers.

I'm struggling with understanding part of this proof.

It makes use of this relationship.

$F_{m + n} = F_{m-1}F_n + F_mF_{n + 1}$

We are supposing that $F_m$ is dvisible by $F_n$ and we have just shown that $F_{nq}$ is divisible by $F_n$. We are trying to proove that m is divisible by n.

So suppose $m = nq + r$

We have $F_m = F_{nq+r} = F_{nq-1}F_{r} + F_{nq}F_{r+1}$

As $F_{nq}$ is divisible by $F_n$ and as $F_m$ is divisible by $F_n$, it follows that $F_n$ divides $F_{nq-1}F_r$

It does? Doesn't the fact that $F_{nq}$ alone mean that $F_n$ divides $F_{nq-1}F_r$? Why do we have to bother with $F_m$?

Then we have

if $gcd(F_{nq-1}, F_n) = 1$ we know by Euclid's Lemma that $F_n$ divides $F_r$. I thought this only work with a prime number? How do we know one of them is prime?