Descent in proof of Euclid's Lemma: prime $\,p\mid bc\Rightarrow p\mid b\,$ or $\,p\mid c$

Question

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:

$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 1

These "direct" proofs of Euclid's Lemma achieve descent via (Euclidean) division with remainder, i.e. we use division to reduce to a smaller instance of the claim, then apply (complete) induction.

The first reduction step replaces any $\,b> p\,$ 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 we still have$\,(b',p) = (b,p) = 1$. The 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.

By the above step(s) we reduce to the case $1 < b < p.\,$ We don't need prime factorizations for descent in this second step. Instead it is more constructive is to replace $\,b\,$ by its smaller remainder $\,p\bmod b = p - qb.\,$

Combining the above two descent steps yield the following variant of the Euclidean algorithm, which applies when one argument is a prime $p\,$ (and $\,p\nmid b)$

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

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

$$\begin{align} &31\mid 38c\\ \Rightarrow\ &\color{#c00}{31\mid 7}c\ \ \ {\rm by}\ \ \ 7 \,=\, 38\bmod 31\ \ \&\ \ \ [\![1]\!]\\ \Rightarrow\ &\color{#c00}{31\mid 3}c\ \ \ {\rm by}\ \ \ 3 \,=\, 31\bmod 7\ \ \ \ \&\ \ \ [\![2]\!]\\ \Rightarrow\ &31\mid 1c\ \ \ {\rm by}\ \ \ 1 \,=\, 31\bmod 3\ \ \ \ \&\ \ \ [\![2]\!] \end{align}\quad\ \ $$

which essentially inlines the following gcd calculation using $[\![1]\!]$ and $[\![2]\!]$

$$(31,38) \,\overset{[\![1]\!]}=\, \color{#c00}{(31,7)\,\overset{[\![2]\!]}=\, (31,3)}\,\overset{[\![2]\!]}=\, (31,1)=1$$

the relation being: $\,31\mid 7c\!\iff\! 31\mid \color{#c00}{(31,7)}c = \color{#c00}{(31,3)}c\!\iff\! 31\mid 3c$

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.

Answer 2

First we want to show that if b is as small as possible, then necessarily b < p. If not, what we can do is subtract c from the factor of a, and get a smaller b$^{\,\prim4} that satisfies out condition.

$$ pa^{\,\prime} = p(a-c) = pa - pc = bc - ac = (b-a)c = b^{\,\prime}c$$.

Thus we can always reduce our value b until b < p. With that in mind, we proceed : We find a prime factor of b, call it q. So q divides bc = pa. q cannot divide p, so p divides a. Since p divides both a and b, we can rewrite our initial equation to get a counter example with values smaller than we had. This is the contradiction that such a prime p exists.