# How did Euclid prove Euclid's Lemma

In Elements, Book VII, Proposition 7, Euclid states: If a number is that part of a number which a subtracted number is of a subtracted number, then the remainder is also the same part of the remainder that the whole is of the whole. He then gives a proof, but the proof isn't clear to me.

The modern version of Euclid's Lemma states that if p is prime and p|ab then either p|a or p|b, or both. I am familiar with the proof by Bezout's Identity, but Euclid didn't know Bezout's Identity.

I am looking for a simple, clear proof of the modern form of Euclid's Lemma, but stated in a way that uses the same concepts as Euclid did. Does anyone have such a proof?

-
The guide section in the link you give seems to imply you have the modern statement wrong. (of course it's true, but it's not what he meant) –  Ben Millwood Sep 18 '12 at 13:36
I don't know what he used, but this trivially follows from unique factorization of integers which, according to Wikipedia, he knew. –  Karolis Juodelė Sep 18 '12 at 13:37
@KarolisJuodelė: it's often used to prove unique factorisation of integers, though. –  Ben Millwood Sep 18 '12 at 13:37
@KarolisJuodelė: Yes, as BenMillwood suggests, I want to use Euclid's Lemma to prove the Fundamental Theorem of Arithmetic, not the other way around. –  user448810 Sep 18 '12 at 13:44
Maybe Euclid didn't know the Bezout's Identity, and maybe he knew. After all, his divine proof of the infinitude of primes resembels the Bezout's identity, that: if $a$ and $b$ are prime, then for some $m$ and $n$ we have $a.m+b.n=1$. –  Hooman Sep 18 '12 at 13:46

I think this is the proof of Euclid's Lemma, and then I go on to prove the Fundamental Theorem of Arithmetic, which is what I first set out to do. The first paragraph proves Euclid's Lemma, the second paragraph proves that all positive integers greater than 1 can be factored into primes, and the third paragraph proves that the factorization is unique, which is the Fundamental Theorem of Arithmetic:

Suppose that a ratio a:b reduces to c:d in lowest terms, assume that c does not divide a, and assume that c(m/n) = a. Since a:b is the same ration as c:d, then d(m/n) = b, which implies that c/m = (1/n)a and d/m = (1/n)b. Therefore c/m:d/m is the same ratio as a:b, which shows that c:d is not in lowest terms. But that contradicts the earlier assumption. Therefore c does divide a, and d divides b the same number of times.

Suppose that a prime p divides the product ab but that p does not divide a, so that p is relatively prime to a. Let n = ab/p; this must be an integer because p|ab. Then p/a = b/n, and p/a must be in lowest terms, because p is relatively prime to a. Thus, by the previous paragraph, there must be some x for which px=b and ax=n, because the two ratios are the same, and therefore p|b. Likewise, if we suppose that p does not divide b, then p|a. Thus, if p is prime and p|ab, then either p|a or p|b.

Suppose that n is the smallest positive integer greater than 1 that cannot be writen as the product of primes. Now n cannot be prime because such a number is the product of a single prime, itself. Thus the composite is n = ab, where both a and b are positive integers less than n. Since n is the smallest number that cannot be written as the product of primes, both a and b must be able to be written as the product of primes. But then n = ab can be written as the product of primes simply by combining the factorizations of a and b. But that contradicts our supposition. Therefore, all positive integers greater than 1 can be written as the product of primes.

Furthermore, that factorization is unique, ignoring the order in which the primes are written. Now suppose that s is the smallest positive integer greater than 1 that can be written as two different products of prime numbers, so that s = p1 * p2 * ... * pm = q1 * q2 * ... * qn. By Euclid's Lemma either p1 divides q1 or p1 divides q2 * ... * qn. Therefore p1 = qk for some k. But removing p1 and qk from the initial equivalence leaves a smaller integer that can be factored in two ways, contradicting the initial supposition. Thus there can be no such s, and all integers greater than 1 have a unique factorization.

Please let me know if I got anything wrong.

EDIT: I added a first paragraph, and modified the second paragraph at the point "there must be some x". The new first paragraph is VII.20, the now-second paragraph is VII.30 (Euclid's Lemma), and the third and fourth paragraphs are the Fundamental Theorem of Arithmetic.

Now is it right?

-
The proof is circular unless you supply a proof of "thus there must be some x...". That's what I refer to as unique fractionization. It is equivalent to Euclid's Lemma and Uniqueness of Prime Factorizations. For proofs and further discussion see the links in my comment to your question. –  Bill Dubuque Sep 18 '12 at 16:21