To find the greatest common measure of two given numbers not relatively prime.

Let *AB* and *CD* be the two given numbers not relatively prime.

It is required to find the greatest common measure of *AB* and *CD.*

If now *CD* measures *AB,* since it also measures itself, then *CD* is a common measure of *CD* and *AB.* And it is clear that it is also the greatest, for no greater number than *CD* measures *CD.*

But, if *CD* does not measure *AB,* then, when the less of the numbers *AB* and *CD* being continually subtracted from the greater, some number is left which measures the one before it.

For a unit is not left, otherwise *AB* and *CD* would be relatively prime, which is contrary to the hypothesis.

Therefore some number is left which measures 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* also measures *DF.* But it measures itself, therefore it also measures the whole *CD.*

But *CD* measures *BE,* therefore *CF* also measures *BE.* And it also measures *EA,* therefore it measures the whole *BA.*

But it also measures *CD,* therefore *CF* measures *AB* and *CD.* Therefore *CF* is a common measure of *AB* and *CD.*

I say next that it is also the greatest.

If *CF* is not the greatest common measure of *AB* and *CD,* then some number *G,* which is greater than *CF,* measures the numbers *AB* and *CD.*

Now, since *G* measures *CD,* and *CD* measures *BE,* therefore *G* also measures *BE.* But it also measures the whole *BA,* therefore it measures the remainder *AE.*

But *AE* measures *DF,* therefore *G* also measures *DF.* And it measures the whole *DC,* therefore it also measures the remainder *CF,* that is, the greater measures the less, which is impossible.

Therefore no number which is greater than *CF* measures the numbers *AB* and *CD.* Therefore *CF* is the greatest common measure of *AB* and *CD.*

Q.E.D.

From this it is clear that, *if a number measures two numbers, then it also measures their greatest common measure.*

Euclid again uses antenaresis (the Euclidean algorithm) in this proposition, this time to find the greatest common divisor of two numbers that aren’t relatively prime. Had Euclid considered the unit (1) to be a number, he could have merged these two propositions into one.

As an illustration consider the problem of computing the greatest common divisor of 884 and 3009. First, repeatedly subtract 884 from 3009 until the remainder is less than 884. An equivalent numerical operation is to divide 884 into 3009; you’ll get the same remainder. In this case after subtracting 884 three times, the remainder is 357. The two numbers under our consideration are now 884 and 357. Repeatedly subtract 357 from 884 to get the remainder 170. Repeatedly subtract 170 from 357 to get the remainder 17. Finally, stop since 17 divides 170. We’ found that GCD(884, 3009) equals 17.

The stages of the algorithm are the same as in VII.1 except that the final remainder *a*_{n+1}, which divides the previous number *a*_{n}, is not 1.

...

(In Euclid’s proof *a*_{1} is *AB, a*_{2} is *CD, a*_{3} is *AE,* and *a*_{4} = *a*_{n+1} is *CF.*)

In the first part of the proof, Euclid shows that since *a*_{n+1} divides *a*_{n}, it also divides *a*_{n-1}, ... , *a*_{2}, and *a*_{1}. Therefore *a*_{n+1} is a common divisor of *a*_{2} and *a*_{1}. In the last part of the proof, Euclid shows that if any number *d* divides both *a*_{2} and *a*_{1}, then it also divides *a*_{3}, ... , *a*_{n}, and *a*_{n+1}. Therefore *a*_{n+1} is the greatest common divisor. The last part of the proof also shows that every common divisor divides the greatest common divisor as noted in the corollary.

There is a similar assumption that the process of antenaresis eventually reaches an end when applied to numbers. Euclid certainly knew it needn’t halt for magnitudes since its halting is used as a criterion for incommensurability (X.2).

There needs to be an explicit axiom to cover these situations. One such axiom is a descending chain condition which states that there is no infinite decreasing sequence of numbers

Note how similar this proposition is to X.3, even having the same diagram and the same corollary. The terminology is slightly different and X.3 deals with magnitudes rather than numbers.