Proof of Divisibilty propery of Fibonaccia numbers.

I'm struggling with understanding part of this proof.

It makes use of this relationship.

We are supposing that is dvisible by and we have just shown that is divisible by . We are trying to proove that m is divisible by n.

So suppose

We have

As is divisible by and as is divisible by , it follows that divides

It does? Doesn't the fact that alone mean that divides ? Why do we have to bother with ?

Then we have

if we know by Euclid's Lemma that divides . I thought this only work with a prime number? How do we know one of them is prime?