If a prime $p\mid ab$, then $p\mid a$ or $p\mid b\ $ [Euclid's Lemma]
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 know 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.
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$.
If $p\not\mid a$, then $\gcd (p,a)=1$ (why?). Since $p\mid ab$ and $\gcd (p,a)=1$, the Euclid's lemma implies that $p\mid b$.