Book 7
1
But AF measures DG; therefore E also measures DG.
1
But it also measures the whole DC therefore it will also measure the remainder CG.
1
But CG measures FH; therefore E also measures FH.
1
But it also measures the whole FA; therefore it will also measure the remainder, the unit AH, though it is a number: which is impossible.
1
Therefore no number will measure the numbers AB, CD; therefore AB, CD are prime to one another. [VII. Def. 12] Q. E. D.
PROPOSITION 2.
2
Given two numbers not prime to one another, to find their greatest common measure.
2
Let AB, CD be the two given numbers not prime to one another.
2
Thus it is required to find the greatest common measure of AB, CD.
2
If now CD measures AB—and it also measures itself—CD is a common measure of CD, AB.
2
And it is manifest that it is also the greatest; for no greater number than CD will measure CD.
2
But, if CD does not measure AB, then, the less of the numbers AB, CD being continually subtracted from the greater, some number will be left which will measure the one before it.
2
For an unit will not be left; otherwise AB, CD will be prime to one another [VII. 1], which is contrary to the hypothesis.
2
Therefore some number will be left which will measure the one before it.
2
Now let CD, measuring BE, leave EA less than itself, let EA, measuring DF, leave FC less than itself, and let CF measure AE.
2
Since then, CF measures AE, and AE measures DF, therefore CF will also measure DF.
2
But it also measures itself; therefore it will also measure the whole CD.
2
But CD measures BE; therefore CF also measures BE.
2
But it also measures EA; therefore it will also measure the whole BA.
2
But it also measures CD; therefore CF measures AB, CD.
2
Therefore CF is a common measure of AB, CD.
2
I say next that it is also the greatest.
2
For, if CF is not the greatest common measure of AB, CD, some number which is greater than CF will measure the numbers AB, CD.
2
Let such a number measure them, and let it be G.
2
Now, since G measures CD, while CD measures BE, G also measures BE.
