I have stumbled upon the following proof of Euclid's Lemma that does not use Bezout's theorem and I have no idea how it proves that $p|a$ or $p|b$.
This is the proof:
Lemma (Euclid). Let p be a prime, and let a, b be integers. If p | ab then p | a or p | b. There are many ways to prove this lemma. First Proof. Assume p is the smallest prime for which this assertion fails, and let a and b be such that p | ab and p ∤ a and p ∤ b. By replacing a and b with their remainders when dividing by p, we may assume that 1 ≤ a < p and 1 ≤ b < p. Then kp = ab; clearly, 1 ≤ k < p. We have k ≠ 1 since p is a prime. Let q be a prime divisor of k. Then q | ab, and so, by the minimality assumption on p, we have q | a or q | b. Then dividing q into k and into one of a or b, we obtain an equation k ′p = a ′ b ′ , where 1 ≤ k ′ < k, 1 ≤ a ′ < p, and 1 ≤ b ′ < p. Repeating this step as long as necessary, we arrive at an equation k ′′p = a ′′b ′′ with k ′′ = 1, 1 ≤ a ′′ < p, and 1 ≤ b ′′ < p. This equation contradicts the primality of p, completing the proof.
Can anyone explain how this proves if $p|ab$ that $p|a$ or $p|b$?
Just noticed that someone has been using a similar process in another question(Proof of Euclid's Lemma)
This is the part that I have trouble understanding:
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.
Can anyone make sense of this?