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?