# Proof of Euclid's Lemma - why does $p$ divide the RHS?

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.

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