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.

  • $\begingroup$ This can be extended to any euclidean domain :P $\endgroup$ – 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$.

  • $\begingroup$ I understand that p divides the first term on the left, but how does it divide the second? $\endgroup$ – cp101020304 Nov 7 '15 at 4:09
  • $\begingroup$ Well, by assumption $p|(kl)$ hence $p|(bkl)$. $\endgroup$ – lulu Nov 7 '15 at 4:11
  • $\begingroup$ Ah, that's so obvious lol! thanks $\endgroup$ – cp101020304 Nov 7 '15 at 4:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.