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?
 A: 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?
