Arguments in proof for Euclid's lemma

Solution 1:

$(p,a)\mid p\,$ so $\,(p,a)\,$ is $\,1\,$ or $\,p,\,$ by $\,p\,$ prime. But $\,(p,a)=p\,\Rightarrow\,p\mid a,\,$ contra hypothesis. Therefore $\,(p,a)=1.\,$ Hence we deduce by the "theorem above" (Bezout's gcd identity) that the gcd may be expressed as an integral linear combination of its arguments, i.e. $$ (p,a)=1\ \Rightarrow\ sp + ta = 1\ \ \text{for some } s,t\in\Bbb Z$$

Scaling the prior Bezout identity by $\,b\,$ we obtain

$$ s\color{#c00}pb + t\color{#c00}{ab} =\color{#0a0} b\qquad $$

Concluding we note that $\,p\mid \color{#c00}{ab}\,\Rightarrow\,p\mid{\rm\color{#c00}{ LHS}}\,\Rightarrow\,p\mid\rm\color{#0a0}{ RHS = b}.\ \ $ QED

Equivalently $\ p\mid pb, ab\,\Rightarrow\, p\mid (pb,ab) = (p,a)b = b\,$ by $\,(p,a)= 1\ $ where we've replaced the use of Bezout identity scaling by the gcd Distributive Law (see here for a few proofs, and see here for a comparison of various forms of Euclid's Lemma in Bezout, gcd and ideal form). This yields a more general proof that works in any gcd domain, e.g. any UFD. But Bezout-based proofs may fail in more general rings where gcds exist but they are not of Bezout linear form, e.g. polynomial rings $\Bbb Z[x]$ or $\,\Bbb Q[x,y],\,$ where $\,(x,y) = 1\,$ but this gcd has no Bezout linear representation $\,xg(x,y) + y f(x,y) = 1,\,$ else evaluation at $\,x = y = 0\,$ yields $\,0 = 1.\,$ Ditto for $(2,x)$ in $\,\Bbb Z[x]$

Alternatively, $\ (\color{}{p,a})=\color{#c00}{\bf 1}\,\Rightarrow\,(\color{#0a0}{p,ab}) = (\color{#c0f}{p,b})\,$ by evaluating the following in two ways

$$\overbrace{(\color{#c0f}p,\ pb}^{\Large \color{#0a0}p},\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\underbrace{\phantom{pb,}\ \color{#0a0}{ab})}_{\quad\Large\color{#c0f}b\,=\, (\!\underbrace{p,a}_{\huge \bf\color{#c00}1}\!)b}\qquad\qquad\qquad\qquad\qquad $$

where we implicitly used the associative and distributive laws of the gcd (see here for more on such gcd "polynomial" arithmetic).