I am having difficulty with the following proof:
The Euclidean algorithm can be used to express $x := gcd(a, b)$ in the form $x = ma + nb$ with $m, n \in Z$.
Use this fact to prove the following: if $p$ is a prime number and $p$ divides the product $kl$ (where $k, l ∈ Z$), then $p$ divides at least one of $k $ and $l$.
I haven't got a clue at all where to start, but I have simple knowledge of Euclid's Lemma but just no idea how to use the expression given in order to prove this.
Say $p$ does not divide $k$. Then gcd$(p,k)=1$. It follows that we can find integers $a,b$ with $$ap+bk=1$$ Multiplying by $l$ yields $$apl+bkl=l$$ As $p$ divides both terms on the left it divides their sum. Hence $p|l$.