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<p$, 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<p$. 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′<b<p$ 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:
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