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.