If prime $p \mid ab$, then $p \mid a$ or $p \mid b\ $ [Euclid's Lemma] The proof is already given in the textbook but I tried other way around. 
Proof by contradiction:
Let's assume that $p$ doesn't divide $a$ and $p$ doesn't divide $b$, but $p$ divides $ab$. So $\gcd(p,a)=1$ and $\gcd(p,b)=1$. Given that we can construct linear combinations 
$sp+ta=1$ together with $up+wb=1$. Multiplying the left and the right sides of the equations we get
$spup+spwb+taup+tawb=1$ or $p(sup+swb+tau)+ab(tw)=1 \implies \gcd(p,ab)=1$. This is a contradiction. 
Is it rigorous and sound proof?
 A: Another elementary proof, which uses only euclidean division.
Let $p$ dividing $ab$, but not $a$. Consider the following set of natural numbers:
$$E=\bigl\{\,n\in \mathbf N^{*}\:;\:p\mid nb\,\bigr\}. $$
$E$ is not empty since it contains $p$ and $a$. Hence it contains a smallest element, $n_0$.
Claim: $n_0$ divides all elements of $E$. Indeed, let $n$ be any element of $E$. We want to prove the remainder of the division of $n$ by $n_0$ is $0$. So let's write:  $n=qn_0+r, \enspace 0\le r <n_0$.
As $p\mid nb$ and $p\mid n_0b$, $p\mid (n-qn_0)b=rb$, hence if $r\neq 0$, $r$ is an element of $E$, which contradicts $n_0$ being minimal. Thus $r=0$ and $n_0\mid n$.
In particular, $n_0\mid p$, hence $n_0=1$ or $p$. The  latter case is impossible by hypothesis, since $n_0\mid a$. So $n_0=1$, and $p\mid n_0b=b$.
A: The proof is correct. Below is the same proof using gcd laws (distributive, etc), for any integer $\,p$.
$\ \ \ \phantom{\frac{.}{\dfrac{.}.}} 1 = \smash[b]{\underbrace{\color{#0a0}{(p,a)}}_{\large =\, 1}\underbrace{(p,b)}_{\large =\, 1} = (\color{#0a0}{(p,a)}p,\color{#0a0}{(p,a)}b) = (p^2,ap,bp,ab) = ((\underbrace{p,a,b}_{\color{#c00}{\large =\,1}})\, p,ab) = (p,ab)} $
where above we have used the inference: $\  (p,a)=1\,\Rightarrow\,(p,a,b)\color{#c00}{ = 1},\,$ and basic gcd arithmetic.
Remark $ $ The following comparison (from here) might prove instructive ($p$ is any integer below)
Euclid's Lemma in Bezout form, gcd form and ideal form
$\quad \smash[t]{\begin{align}\\ \\ 
px\!+\!ay=&\,\color{#c00}1,\,\ p\ \mid\ ab\ \ \ \Rightarrow\, p\ \mid\ b.\ \ \ {\bf Proof}\!:\,\ p\ \mid\  pb,ab\, \Rightarrow\,  p\,\mid pbx\!\!+\!aby = \!(\overbrace{px\!+\!ay}^{\large\color{#c00} 1}\!) b = b\\[.2em]
(p,\ \ \ a)=&\,\color{#c00}1,\,\ p\ \mid\ ab\ \ \ \Rightarrow\, p\ \mid\ b.\ \ \ {\bf Proof}\!:\,\ p\ \mid\  pb,ab\, \Rightarrow\,  p\,\mid (pb,\ \ ab) = (p,\,\ \ \ a) \ b =\, b\\[.2em]
P\! +\!A\ =&\,\color{#c00}1,\, P\supseteq AB\, \Rightarrow P \supseteq B.\   {\bf Proof}\!:\!   P \supseteq\! PB,\!AB\!\Rightarrow\!\! P\supseteq\! PB\!+\!\!AB =(P\!+\!A)B = B 
\end{align}}$
Note how the Distributive Law for integers is replaced by the Distributive Law for gcds and ideals in the $2$nd last equality in the proofs.
Generally $\,\ c\mid ab\iff c/(c,a)\mid b\,$ by here, or even more generally for both  gcds and ideals we have $\,(c,ab) = (c,(a,c)b).\,$  OP is special case $\,(c,as)=1\,$ (for $\,c\,$ prime).
A: I hope that it is also another elementary proof of this lemma :
Let's assume that $p$ (a prime number) doesn't divide $a$ and $p$ doesn't divide $b$.
That means that $\exists\ (k_1,r_1), (k_2,r_2) \in \mathbb{Z}\times\mathbb{Z}^*$ such as :
$a=pk_1+r_1$ with $0<\vert r_1 \vert<p$ and $b=pk_2+r_2$ With $0<\vert r_2\vert <p$
$\Rightarrow$ $ab=(pk_1+r_1)(pk_2+r_2)=p(pk_1 k_2 + k_1 r_2 + k_2 r_1)+r_1 r_2 = pK+R$ 
$p$ doesn't divide $R$. Indeed if $p$ divided $R=r_1 r_2$ with $\gcd(p,r_1)=1$ by Gauss Lemma $p$ should divide $r_2$. Impossible.
Hence, $p$ doesn't divide $ab$.
I conclude by contraposition that : if $p$ doesn't divide $a$ and $p$ doesn't divide $b$ then $p$ doesn't divide $ab$.
With this method, I can easily generalize this lemma to $n$ numbers : "If $p$ is a prime number which divides $a_1 a_2 ... a_n$ then $p$ divides $a_1$ or ... or $a_n$".
NB : It will just work in Euclidean Domains like $\mathbb{Z}$.
A: Here is an alternative proof. It is easiest to derive Euclid's lemma as a corollary of the following, more general, result:

If $n\mid ab$ and $n$ is coprime with $a$, then $n \mid b$.

One proof of the above uses Bezout's identity. Since $n$ and $a$ are coprime, there are integers $x$ and $y$ such that $nx+ay=1$. Hence, $nxb+ayb=b$. Since $n$ divides both $nxb$ and $ayb$, it follows that $n \mid b$.
Now suppose $n$ is a prime $p$, and that $p \mid ab$. If $p$ and $a$ are coprime, then $p \mid b$. If $p$ and $a$ are not coprime, then there is a $k>1$ such that $k\mid p$ and $k\mid a$. Since $p$ is prime, it follows that $k=p$ and so $p \mid a$. Hence, regardless of whether $p$ and $a$ are coprime, either $p \mid a$ or $p \mid b$ (or both).
