# Thread: 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.

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

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

So suppose $\displaystyle m = nq + r$

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

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

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

Then we have

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