If a prime $p\mid ab$, then $p\mid a$ or $p\mid b\ $ [Euclid's Lemma] If a prime number $p$ is a divisor of a product $ab$, $p$ has to be a divisor of $b$ or $a$. How can I demonstrate this theorem? I demonstrated this theorem on one way using Bezout's theorem in an answer below but are there other proofs??
The set $\,S\,$ of naturals $\,n\,$ such that $\,\color{#c00}{p\mid nb}\,$ is $\rm\overbrace{closed\ under\ subtraction}^{\overbrace{\large p\mid nb,kb\,\Rightarrow\, p\mid nb-kb\, =\, (n-k)b}^{\LARGE n,\,k\ \in\ S\ \ \ \Longrightarrow\ \ \ n-k\ \in\ S\ \ }}$ and $\, a,p\in S\,$ therefore by the Lemma its least positive element $\,\color{#0a0}{d\mid a,p}.\,$ Since $\,\color{#a0f}{d\mid p\ \ \rm prime},\,$ either $\,\color{#a0f}{d=p}\,$ (so $\ \color{#a0f}{p = }\color{#0a0}{d\mid a}),\,$ or $\,\color{#a0f}{d=1}\in S\ $ (so $\ \color{#c00}{p\mid d b = b}),\ $ i.e. $\,\ p\mid \color{}a\,$ or $\ p\mid \color{}b.\ \ $ QED

Lemma $\ \ $ Let $\,\rm S\ne\emptyset \,$ be a set of integers $&gt;0$ closed under subtraction $&gt; 0,\,$ i.e. for all $\rm\,n,m\in S, \,$ $\rm\ n &gt; m\ \Rightarrow\  n-m\, \in\, S.\,$  Then the least $\rm\:\ell\in S\,$ divides every element of $\,\rm S.$
Proof ${\bf\ 1}\,\  $ If not there is a least nonmultiple $\rm\,n\in S,\,$ contra  $\rm\,n-\ell \in S\,$ is a nonmultiple of $\rm\,\ell.$
Proof ${\bf\ 2}\,\rm\,\ \   S\,$ closed under subtraction $\rm\,\Rightarrow\,S\,$ closed under remainder (mod), when it is $\ne 0,$ since mod is simply repeated subtraction, i.e. $\rm\ a\ mod\ b\, =\, a - k b\, =\, a\!-\!b\!-\!b\!-\cdots\! -\!b.\,$ Thus $\rm\,n\in S\,$ $\Rightarrow$ $\rm\, (n\ mod\ \ell) = 0,\,$ else it is in $\,\rm S\,$ and smaller than $\rm\,\ell,\,$ contra minimality of $\rm\,\ell.$

Remark $\ $ In a nutshell, two applications of induction yield the following inferences
$\begin{eqnarray}\rm S\ closed\ under\ {\bf subtraction} &amp;\Rightarrow\:&amp;\rm S\ closed\ under\ {\bf mod} = remainder = repeated\ subtraction \\
&amp;\Rightarrow\:&amp;\rm S\ closed\ under\ {\bf gcd} = repeated\ mod\ (Euclid's\ algorithm) \end{eqnarray}$
Interpreted constructively, this yields the extended Euclidean algorithm for the gcd.
If fractions are known then $\,S\,$ can be interpreted as the set of all possible denominators of $\,b/p,\,$ since $\,ap = nb \iff a/n = b/p.\,$ See various posts on denominators ideals for more.
The Lemma describes a fundamental property of integer arithmetic whose essence will become clearer when one studies ideals of rings, viz. a Euclidean domain  is a PID, i.e. in any domain $D$ enjoying a Euclidean algorithm for division with remainder, all ideals $I$ are principal, i.e. $\, I = dD\,$ where $d$ is the least nonzero element of the ideal (= gcd of all elements). Here a subset $\,I\subset D$ is an ideal if is closed under subtraction and scaling by elements of $D$. The proof is exactly as in the 2nd proof above - by Euclidean descent using remainder (mod) via the division algorithm, e.g. see here and here and here.
See here for a few alternative proofs.
See here for a precise comparison of various forms of Euclid's Lemma
Variations of the above Theorem yield analogous &quot;direct proofs&quot; of the Fundamental Theorem of Arithmetic (existence and uniqueness of prime factorizations of integers), e.g. see this answer. Various forms of such direct proofs were given by Klappauf, Lindemann, and Zermelo.
$ab$ contains p as it's prime factor. That's what $p|ab $ means. Since $p$ is prime, it can't be expressed as product of two numbers except $1$ and $p$.  So either $a $ should contain it or $ b$.