# euclidian algorithm proof

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.

• This can be extended to any euclidean domain :P – Zelos Malum Nov 7 '15 at 4:13

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$.
• Well, by assumption $p|(kl)$ hence $p|(bkl)$. – lulu Nov 7 '15 at 4:11