elementary number theory - Euclid proof explanation

Can anyone help me understand the following proof that if $p|ab$ then $p|a$ or $p|b$? This proof is on a separate question.

Suppose there were a counterexample, with $pa=bc$, $p$ a prime, but
neither $b$ nor $c$ divisible by $p$. Then there would be a counterexample
with $p$ as small as possible and, for that $p$, $b$ as small as possible.
Note that $b>1$, since otherwise we would have $pa=c$, which means $p$
divides $c$.

We first note that $b, since otherwise $pa′=p(a−c)=(b−p)c=b′c$ would be
a smaller counterexample. But now $b>1$ implies $b$ is divisible by some
prime $q$, which means we have $q$ dividing pa with $q≤b. By the
minimality of $p$ as a counterexample, we conclude that $q$ divides $a$
(since it can't divide $p$). If we now write $a=a′q$ and $b=b′q$ and note
that $b′ implies $p$ doesn't divide $b′$ either, we find that $pa′=b′c$
is a smaller counterexample, which is a contradiction. Thus there can
be no counterexample.

I am having trouble understanding how this proves anything. Especially this part:

$pa′=p(a−c)=(b−p)c=b′c$

What is the reasoning behind subtracting $c$ and $p$ from the factors? Would someone be willing to go through this proof step by step and explain why it works?

Question: Proof of Euclid's Lemma

Answer

These "direct" proofs of Euclid's Lemma all achieve descent via the division algorithm. The first step is to reduce to a smaller problem when $\,b> p\,$ by replacing it by a smaller $\,b'\equiv b\pmod{p},\,$ which doesn't alter the truth of the statement since $\,p\mid bc\iff p\mid b'c,\,$ and $\,(b',p) = (b,p) = 1$.

OP chooses $\,b' = b-p,\,$ but we could also choose $\,b' = b\bmod p < p\,$ as in the equivalent proof you posted a few days ago. Further when $1 < b < p$ we don't need prime factorizations for descent. More constructive is to replace $\,b\,$ by $\,p\bmod b = p - qb.\,$ Then the two descent steps amount to the following variant of the Euclidean algorithm when one argument is a prime $p$ and $\,p\nmid b$

$$\begin{align} &(b,p) = (b\bmod p,\,p)\ \ {\rm if}\ \ b > p\\[.3em]
&(b,p) = (p\bmod b,\,p)\ \ {\rm if}\ \ b < p\end{align}$$

This form of the proof essentially uses $\,p\mid bc\,\Rightarrow\, p\mid(b,p)c = c\,$ by $\,(b,p) = 1,\,$ while using the above two descent steps to calculate the gcd $(b,p) = 1.\,$ Here is a simple concrete example.

$$\begin{align}
&31\mid 38c\\
\iff\ &31\mid 7c\ \ \ {\rm by}\ \ \ 7 \,=\, 38\bmod 31\\
\iff\ &31\mid 3c\ \ \ {\rm by}\ \ \ 3 \,=\, 31\bmod 7\\
\iff\ &31\mid 1c\ \ \ {\rm by}\ \ \ 1 \,=\, 31\bmod 3
\end{align}\qquad$$

Eliminating the (unneeded) contradictive form and viewing it positively leads to Gauss's algorithm for computing inverses and fractions $\!\bmod p$

See also this closely related proof.