If $p$ is a prime and $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?

Solution 1:

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}.$

Remark $\ $ The following comparison might prove instructive.

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).

Solution 2:

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$.