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.
Best Answer
In Book VII you'll find
When you read these definitions it appears that Euclid's definition is an axiomatic statement:
$\quad$ IF $a \lt b$ THEN $[ \,a \text{ is a part of } b\,] \text{ xor } [\,a \text{ is parts of } b\,]$.
In the guide to the above definitions you'll find
So I think Euclid felt the need for an $\text{XOR}$ algorithm that could decide the matter for any two distinct numbers. Lurking behind this is that he won't be defining rational numbers as an equivalence relation on a set - he needs to calculate a a canonical representation/idea/concept.
Euclid's logic of not regarding $1$ as a number also plays a part in this. My guess is that an attempt was being made to 'compartmentalize' concepts and to avoid trivial statements. For Euclid the number, say five, is a multitude of units. He doesn't want to also say that one is a part of five.
It is interesting how liberating the logic becomes, when, in modern mathematical treatments we don't ignore or shortchange the trivial numbers $1$ or $0$. Euclid would certainly be amazed to see how much things open up once we can all agree on the existence of the empty set.