Euclid, Elements
Thomas L. Heath, Sir Thomas Little Heath, Ed.

PROPOSITION 2.

Let AB, CD be the two given numbers not prime to one another.

Thus it is required to find the greatest common measure of AB, CD.

If now CD measures AB—and it also measures itself—CD is a common measure of CD, AB.

And it is manifest that it is also the greatest; for no greater number than CD will measure CD.

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.

For an unit will not be left; otherwise AB, CD will be prime to one another [VII. 1], which is contrary to the hypothesis.

Therefore some number will be left which will measure the one before it.

Now let CD, measuring BE, leave EA less than itself, let EA, measuring DF, leave FC less than itself, and let CF measure AE.

Since then, CF measures AE, and AE measures DF, therefore CF will also measure DF.

But it also measures itself; therefore it will also measure the whole CD.

But CD measures BE; therefore CF also measures BE.

But it also measures EA; therefore it will also measure the whole BA.

But it also measures CD; therefore CF measures AB, CD.

Therefore CF is a common measure of AB, CD.

I say next that it is also the greatest.

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.

Let such a number measure them, and let it be G.

Now, since G measures CD, while CD measures BE, G also measures BE.

But it also measures the whole BA; therefore it will also measure the remainder AE.

But AE measures DF; therefore G will also measure DF.

But it also measures the whole DC; therefore it will also measure the remainder CF, that is, the greater will measure the less: which is impossible.

Therefore no number which is greater than CF will measure the numbers AB, CD;

PORISM.

Q. E. D.