# Euclid lemma proof without Bezout's theorem

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

EDIT:

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, 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.

Can anyone make sense of this?

• It doesn't. "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" That is never true. – Steve B Oct 24 '18 at 11:00
• @SteveB: Why not? If $p | ab$ and $a=pq_a+r_a$, $b=pq_b+r_b$, then $ab=p(p q_a q_b+q_a r_b+q_b r_a)+r_a r_b$ and $p | r_a r_b$. – metamorphy Oct 24 '18 at 11:10
• But after "Then dividing q into k..." there's a mess indeed. – metamorphy Oct 24 '18 at 11:14
• @metamorphy, but if $p | r_a r_b$, then by the very theorem being proved, $p | r_a$ or $p | r_b$. So one of $r_a$ and $r_b$ is not the remainder when any integer is divided by p. – Steve B Oct 24 '18 at 11:23
• @SteveB: Yes, but we don't know it yet. And it is not supposed to happen in fact, as we're going to produce a contradiction! – metamorphy Oct 24 '18 at 11:25