I'm looking for a reference containing the following proof of Euclid's Lemma.

Recall the statement: Let $a,b$ be positive integers and let $p$ be a prime dividing $ab$. Then $p$ divides $a$ or $b$.

[I'm rewriting the proof taking into account Geoff Robinson's comments:]

Let $Q$ be the set of those quadruples $(p,c,a,b)$ of positive integers such that

  • $p$ is prime,

  • $ab=pc$,

  • $p$ divides neither $a$ nor $b$.

Assume by contradiction that $Q$ is nonempty and let $(p,c,a,b)$ be its least element with respect to the lexicographical ordering. We clearly have $c > 1$. We also have $c < p$ because otherwise $(p,c-a,a,b-p)$ would be in $Q$.

[Edit (Aug. 4): Assuming $c\ge p$, we have $b > p$ (and thus $c > a$), for the contrary would imply $a\le b < p$, and thus $ab < p^2\le pc=ab$. (Thank you to Bill Dubuque!)]

If $q$ is a prime factor of $c$, then $(p,c/q,a/q,b)$ or $(p,c/q,a,b/q)$ is in $Q$, a contradiction.

EDIT (July 24). Thank you to Martin Sleziak for his comments. I'll look quietly at his links, and make perhaps a new edit. In the meantime here is the argument used by Gauss in his Disquisitiones Arithmeticae, Art. 13. [I should have studied this Article more seriously before posting my question. My apologies.]

Let $p$ be a prime and $a$ a positive integer not divisible by $p$. Assume by contradiction that the set $B$ of all positive integers $x$ such that $p$ divides $ax$, but doesn't divide $x$, is nonempty, and let $b$ be the minimum of $B$. The inequalities $1 < b < p$ are clear. There is a positive integer $m$ such that $mb < p < (m+1)b$, and one easily checks that $p-mb$ is less than $b$ and belongs to $B$, a contradiction. QED

Actually I like Gauss's argument much better than the one I gave above. But here is what puzzles me. Many Elementary Number Theory and Algebra textbooks prove the Fundamental Theorem of Arithmetic (or Euclid's Lemma) using only Peano like axioms, and in particular not using the construction of $\mathbb Z$ from $\mathbb N$. I find it's a very good idea to do so. [I agree that the construction of $\mathbb Z$ is of paramount importance, but I believe, it's also important to realize that the Fundamental Theorem doesn't rely on it.] The trouble is that these proofs, I feel, tend to be much more complicated than the above argument of Gauss. [Thank you for correcting me if I'm wrong.]

  • $\begingroup$ @Geoff Robinson - Thanks for your comment. I tried to make things less cryptic by adding an edit. $\endgroup$ – Pierre-Yves Gaillard Jul 23 '11 at 11:27
  • 1
    $\begingroup$ Yes, thanks, that clarifies it. I slightly re-edited my comment, since I was cut off last time. I suppose your argument is somewhat in the tradition of Fermat- if there is a solution, there is a minimal one, but then you can produce a smaller one. You could almost says yours is a proof "by induction on the prime"- take p as the minimal prime for which the Lemma fails (note that p =2 is OK!). $\endgroup$ – Geoff Robinson Jul 23 '11 at 15:15
  • 1
    $\begingroup$ Trouble editing, but (for the record), here's what my first comment was meant to be:"Your proof is a little cryptic, but the idea is very nice. I suppose what you meant was that $a <p$ and $b <p$, and that $c$ has no common factor with $a$ or $b$." $\endgroup$ – Geoff Robinson Jul 23 '11 at 15:25
  • 1
    $\begingroup$ @Pierre-Yves: I added my comments as an answer. I think you might want to wait with accepting the answer - perhaps someone will have something interesting to say about your last paragraph. $\endgroup$ – Martin Sleziak Jul 25 '11 at 7:05
  • 1
    $\begingroup$ @Bill Dubuque - I was wondering: do you have an estimate of the total number of your posts (on the whole web)? $\endgroup$ – Pierre-Yves Gaillard Aug 4 '11 at 17:47

I tried to google for "euclid's lemma" "divides neither". It seems that wikipedia provides similar proof in the part "Alternate proof without Bézout's identity", but it does not give a reference. Also this paper contains a proof similar to yours, but not exactly the same.

I was about to suggest to ask the editor which contributed this proof to wikipedia article about the source, but it seems that this edit was anonymous. I think that if you find a textbook containing this proof, it would be a good idea to add it as a reference to wikipedia article.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.