[proofplan]
We argue by cases on whether $p \mid a$. If $p \mid a$ the conclusion holds directly, so we may assume $p \nmid a$. Primality of $p$ then forces $\gcd(a, p) = 1$, which by [Bezout's Lemma](/theorems/???) produces an integer identity $ar + ps = 1$. Multiplying this identity by $b$ exhibits $b$ as an integer combination of $ab$ and $p$, both of which are divisible by $p$, so $p \mid b$.
[/proofplan]
[step:Reduce to the case $p \nmid a$]
We prove the statement $p \mid a$ or $p \mid b$ by case analysis on whether $p$ divides $a$. If $p \mid a$, the conclusion holds and there is nothing further to prove. Henceforth assume
\begin{align*}
p \nmid a.
\end{align*}
Under this assumption we will deduce $p \mid b$.
[/step]
[step:Deduce $\gcd(a, p) = 1$ from primality of $p$ and $p \nmid a$]
Let $d := \gcd(a, p) \geq 1$. Then $d \mid p$. Since $p$ is prime, its only positive divisors are $1$ and $p$, so $d \in \{1, p\}$. If $d = p$, then $p = d \mid a$, contradicting the assumption $p \nmid a$. Therefore $d = 1$, i.e.,
\begin{align*}
\gcd(a, p) &= 1.
\end{align*}
[guided]
We want to exploit $p \nmid a$ to conclude $a$ and $p$ are coprime. Let $d := \gcd(a, p) \geq 1$; by definition $d \mid a$ and $d \mid p$. The second condition is decisive: the prime $p$ admits only two positive divisors, namely $1$ and $p$ itself. Thus $d = 1$ or $d = p$.
If $d = p$, then from $d \mid a$ we obtain $p \mid a$, contradicting our standing assumption that $p \nmid a$. The only remaining possibility is $d = 1$, so
\begin{align*}
\gcd(a, p) &= 1.
\end{align*}
This is the crucial bridge: primality of $p$ converts the qualitative non-divisibility $p \nmid a$ into the quantitative coprimality $\gcd(a, p) = 1$, which in turn unlocks Bezout.
[/guided]
[/step]
[step:Apply Bezout's lemma to obtain an integer identity $ar + ps = 1$]
By [Bezout's Lemma](/theorems/???) applied to the integers $a$ and $p$, there exist $r, s \in \mathbb{Z}$ such that
\begin{align*}
ar + ps &= \gcd(a, p).
\end{align*}
Bezout's lemma requires only that not both arguments are zero, which holds since $p \geq 2$. Using the conclusion $\gcd(a, p) = 1$ from Step 2,
\begin{align*}
ar + ps &= 1.
\end{align*}
[/step]
[step:Multiply by $b$ and exhibit $b$ as a $\mathbb{Z}$-linear combination of $ab$ and $p$]
Multiplying the identity $ar + ps = 1$ by $b$ gives
\begin{align*}
b &= (ab)\, r + p\, (bs).
\end{align*}
By hypothesis $p \mid ab$, and $p \mid p$ since every integer divides itself. Since divisibility is closed under integer linear combinations,
\begin{align*}
p \mid \bigl( (ab)\, r + p\, (bs) \bigr) = b.
\end{align*}
Hence $p \mid b$, completing the case $p \nmid a$. Combined with Step 1, we conclude $p \mid a$ or $p \mid b$.
[guided]
We have the Bezout identity $ar + ps = 1$. The trick to "activate" the hypothesis $p \mid ab$ is to multiply through by $b$, which introduces the product $ab$ into the equation:
\begin{align*}
b &= arb + psb = (ab)\, r + p\, (bs).
\end{align*}
Both terms on the right are manifestly divisible by $p$: the first because $p \mid ab$ (the hypothesis of the theorem), the second because $p \mid p$. Divisibility is closed under integer linear combinations — if $p \mid x$ and $p \mid y$, then $p \mid (\alpha x + \beta y)$ for all $\alpha, \beta \in \mathbb{Z}$ — so
\begin{align*}
p \mid \bigl((ab)\, r + p\, (bs)\bigr) = b.
\end{align*}
This yields $p \mid b$. Combined with the alternative $p \mid a$ from Step 1, we have shown $p \mid a$ or $p \mid b$.
A remark on what primality was used for. The proof used primality exactly once, in Step 2, to rule out intermediate divisors of $p$. For a composite modulus $n$, the argument breaks down: if $n = 6$, then $6 \mid 2 \cdot 3$ but $6 \nmid 2$ and $6 \nmid 3$, reflecting the fact that $\gcd(2, 6) = 2 \neq 1$.
[/guided]
[/step]
