If a prime $p\mid ab$, then $p\mid a$ or $p\mid b\ $ [Euclid's Lemma]

Solution 1:

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 $>0$ closed under subtraction $> 0,\,$ i.e. for all $\rm\,n,m\in S, \,$ $\rm\ n > 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} &\Rightarrow\:&\rm S\ closed\ under\ {\bf mod} = remainder = repeated\ subtraction \\ &\Rightarrow\:&\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 "direct proofs" 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.

Solution 2:

Here is one, which uses only euclidean division and the well-order on $\mathbf N$:

Let $E = \bigl\{x ∈ \mathbf N^{\boldsymbol *} \mid p\enspace \text{divides}\enspace xb\}$ . $E$ is not empty, since it contains at least $p\,$ and $\,a $.Thus it contains a smallest element, $x_0$.

This element divides each $x\in E$: indeed the euclidean division of $x$ by $x_0$ gives: $\,x = qx_0 + r\enspace(0 ≤ r < x_0)$. As $x, x_0$ are in $E$, $p$ divides $xb$ and $x_0b$, hence $(x-qx_0)b =rb$. Thus, if $r\neq 0$, $r\in E$. This is impossible since $x_0$ is the smallest element in $E$. So $r = 0$ i.e. $\,x_0$ divides $x$.

In particular, $x_0$ divides $p$ et $a $, which belong to $E$ ; as $p$ and $a $ are coprime, $x_0 = 1$. Thus, $p$ divides $x_0 b = b$.