Two unequal numbers being set out, and the less being continually subtracted in turn from the greater, if the number which is left never measures the one before it until an unit is left, the original numbers will be prime to one another.
For, the less of two unequal numbers / A B /, / C D / being continually subtracted from the greater, let the number which is left never measure the one before it until an unit is left;
I say that / A B /, / C D / are prime to one another, that is, that an unit alone measures / A B /, / C D /.
For, if / A B /, / C D / are not prime to one another, some number will measure them.
Let a number measure them, and let it be E; let / C D /, measuring / F B /, leave / A F / less than itself, let / A F /, measuring / G D /, leave / C G / less than itself, and let / C G /, measuring / H F /, leave an unit / A H /.
Since, then, E measures / C D /, and / C D / measures / F B /,
therefore E also measures / F B /.
But it also measures the whole / A B /;
therefore it will also measure the remainder / A F /.
But / A F / measures / G D /;
therefore E also measures / G D /.
But it also measures the whole / C D /;
therefore it will also measure the remainder / C G /.
But / C G / measures / H F /;
therefore E also measures / H F /.
But it also measures the whole / A F /;
therefore it will also measure the remainder, the unit / A H /, though it is a number: which is impossible.
Therefore no number will measure the numbers / A B /, / C D /; therefore / A B /, / C D / are prime to one another. [G.249]
