Euclid's Elements, Book VII, Proposition 1

Proposition 1

When two unequal numbers are set out, and the less is continually subtracted in turn from the greater, if the number which is left never measures the one before it until a unit is left, then the original numbers are relatively prime.
The less of two unequal numbers AB and CD being continually subtracted from the greater, let the number which is left never measure the one before it until a unit is left.
I say that AB and CD are relatively prime, that is, that a unit alone measures AB and CD.		VII.Def.12
If AB and CD are not relatively prime, then some number E measures them. Let CD, measuring BF, leave FA less than itself, let AF, measuring DG, leave GC less than itself, and let GC, measuring FH, leave a unit HA.
Since, then, E measures CD, and CD measures BF, therefore E also measures BF. But it also measures the whole BA, therefore it measures the remainder AF. But AF measures DG, therefore E also measures DG. But it also measures the whole DC, therefore it also measures the remainder CG. But CG measures FH, therefore E also measures FH. But it also measures the whole FA, therefore it measures the remainder, the unit AH, though it is a number, which is impossible.
Therefore no number measures the numbers AB and CD. Therefore AB and CD are relatively prime.		VII.Def.12
Therefore, when two unequal numbers are set out, and the less is continually subtracted in turn from the greater, if the number which is left never measures the one before it until a unit is left, then the original numbers are relatively prime.
Q.E.D.

Modern terminology uses the word "divides" rather than "measures," and the notation a | b is used to abbreviate the phrase "a divides b."

This proposition assumes that 1 is the result of an antenaresis process. Antenaresis, also called the Euclidean algorithm, is a kind of reciprocal subtraction. Beginning with two numbers, the smaller, whichever it is, is repeatedly subtracted from the larger.

If the initial two numbers are a₁ (AB in the proof) and a₂ (CD), with a₁ greater than a₂, then the first stage is to repeatedly subtract a₂ from a₁ until a remainder a₃ (AF) less than a₂ is found. That can be stated algebraically as

a₁ = m₁ a₂ + a₃ where m₁ is the number of times that a₂ was subtracted from a₁.

The next stage repeatedly subtracts a₃ from a₂ leaving a remainder a₄ (CG):

a₂ = m₂ a₃ + a₄.

For the hypotheses of this proposition, the algorithm stops when a remainder of 1 occurs:

a_n-1 = m_n-1 a_n + 1. (In Euclid's proof, a_n is a₅ which is AH.) The conclusion is that a₁ and a₂ are relatively prime.

The proof is not difficult. It depends on the observation that if b divides (that is, measures) both c and d, then b divides their difference c - d. So, if some number b divides both a₁ and a₂, then it divides the remainder a₃, too. And since it divides both a₂ and a₃, it divides the remainder a₄. And so forth, with the final conclusion that b divides the last remainder 1.

Since there is no number b (and by "number" is meant a number greater than 1) which divides 1, there is no number that divides both a₁ and a₂. Therefore a₁ and a₂ are relatively prime.

Compare this proposition to X.2, a somewhat analogous statement about magnitudes.

This proposition is used in the proof of the next one.

Book VII Introduction - Definition VII.Def.22 - Proposition VII.2.