I'm trying to understand the following proof of Euclid's lemma.

Claim: If $p$ is a prime that divides $ab$, then $p$ divides $a$ or $p$ divides $b$.

Proof: If we suppose that $p$ does not divides $a$, then this implies there are integers $s$ and $t$ such that $$\gcd(a,p) = 1 = as + pt$$

Now, multiplying $b$ on both sides

$$b= abs + bpt$$

From this, it can be seen that $p$ divides the right hand side of the equation and so must also divide $b$.

I do not understand the "$p$ divides the right hand side of the equation". I tried looking back to the theorem that states the the gcd of two integers $a$ and $b$ is a linear combination but unable to bridge the understanding.


Since $p$ divides $ab$, there is some $k \in \mathbb Z$ such that $ab = kp$. Hence, since: $$ b = abs + bpt = (kp)s + bpt = p\underbrace{(ks + bt)}_{\in ~ \mathbb Z} $$ we conclude that $p$ divides $b$, as desired.

  • $\begingroup$ Missing piece of that puzzle. $\endgroup$ – Mathematicing Dec 31 '15 at 10:04

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.