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?

  • $\begingroup$ 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. $\endgroup$ – Steve B Oct 24 '18 at 11:00
  • 1
    $\begingroup$ @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$. $\endgroup$ – metamorphy Oct 24 '18 at 11:10
  • $\begingroup$ But after "Then dividing q into k..." there's a mess indeed. $\endgroup$ – metamorphy Oct 24 '18 at 11:14
  • $\begingroup$ @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. $\endgroup$ – Steve B Oct 24 '18 at 11:23
  • $\begingroup$ @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! $\endgroup$ – metamorphy Oct 24 '18 at 11:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.