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