# Euclid proof explanation

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

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

• $p\mid ab\Longrightarrow (p\mid a)\vee (p\mid b)$ is the definition of prime. – Jack D'Aurizio Oct 27 '18 at 14:12
• Since $pa=bc$ we have $p(a-c)=pa-pc=bc-pc=(b-p)c$. If $b>p$ then this would be a smaller counterexample. Is that what you were asking? – lulu Oct 27 '18 at 14:12
• (a) If there is a counterexample, there is a smallest; (b) if there is a counterexample there is a smaller one - therefore there is no smallest. Therefore there is no counterexample. – Mark Bennet Oct 27 '18 at 14:31
• @JackD'Aurizio I agree. But "prime" is used in a lot of elementary work to mean "irreducible", and only later are the two properties properly distinguished. So it is not surprising to see the term "prime" being used loosely in this context. – Mark Bennet Oct 27 '18 at 14:34
• Well, if $b>p$ then $b>b-p>0$. we see that $p\,|\,(b-p)c$ so either $p\,|\,c$ or $p\,|\,b-p$. But $p$ can't divide $c$ by the original assumption on $bc$, so $p$ must divide $b-p$. But in that case it is easy to see that $p\,|\,b$, which again contradicts the assumption. – lulu Oct 27 '18 at 14:40

## 2 Answers

These "direct" proofs of Euclid's Lemma all achieve descent via the division algorithm. The first step is to reduce to a smaller problem when $$\,b> p\,$$ by replacing it 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 $$\,(b',p) = (b,p) = 1$$.

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. Further when $$1 < b < p$$ we don't need prime factorizations for descent. More constructive is to replace $$\,b\,$$ by $$\,p\bmod b = p - qb.\,$$ Then the two descent steps amount to the following variant of the Euclidean algorithm when one argument is a prime $$p$$ and $$\,p\nmid b$$

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

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

\begin{align} &31\mid 38c\\ \iff\ &31\mid 7c\ \ \ {\rm by}\ \ \ 7 \,=\, 38\bmod 31\\ \iff\ &31\mid 3c\ \ \ {\rm by}\ \ \ 3 \,=\, 31\bmod 7\\ \iff\ &31\mid 1c\ \ \ {\rm by}\ \ \ 1 \,=\, 31\bmod 3 \end{align}\qquad

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.

• Why were you able to replace $b$ by $p$ $mod$ $b$? – Michael Munta Oct 30 '18 at 21:21
• @Michael That's explained in the 2nd sentence "which doesn't alter...". Ditto for reducing $b$ to $b-p$ (note $b\bmod p = b-kp$ can be viewed as an iteration of that till we reach the remainder $r = b\bmod$p).\ \ $– Bill Dubuque Oct 30 '18 at 21:55 • @Michael Your quoted proof uses the above Euclidean descent only in the first half - to reduce to the case$\,b < p\, $(essentially by repeatedly subtracting$\,p\,$from$b$, i.e. by replacing$\,b\,$by$\,b\bmod p).\,$After that it uses prime factorization. But as I show above we can continue to use the Euclidean descent in the case$\,b < p.\ $– Bill Dubuque Dec 25 '18 at 17:20 • @Michael You can read Gauss's Disq. Artth. proof in Google Books. Art.13 p. 5 employs the descent$\,p\mid ab\,\Rightarrow\, p\mid a(p\bmod b)$to decrease$b$when$\,1<b<p.\ $– Bill Dubuque Dec 31 '18 at 16:14 • @Michael$\ 31\ $divides each of$\ 7c > 3c > c\ \ $– Bill Dubuque Dec 31 '18 at 16:29 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.