Coprimality Criterion

Theorem

As Euclid defined it:

Two unequal (natural) 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.

(The Elements: Book VII: Proposition $1$)

Proof

Let the less of two unequal numbers $AB, CD$ be continually subtracted from the greater, such that the number which is left over never measure the one before it till a unit is left.

We need to show that $AB$ and $CD$ are coprime.

Suppose $AB, CD$ are not coprime.

Then some natural number $E > 1$ will divide them both.

Let some multiple of $CD$ be subtracted from $AB$ such that the remainder $AF$ is less than $CD$.

Then let some multiple of $AF$ be subtracted from $CD$ such that the remainder $CG$ is less than $AF$.

Then let some multiple of $CG$ be subtracted from $FA$ such that the remainder $AH$ is a unit.

Since, then, $E$ divides $CD$, and $CD$ divides $BF$, then $E$ also divides $BF$.

But $E$ also divides $BA$.

Therefore $E$ also divides $AF$.

But $AF$ divides $DG$.

Therefore $E$ also divides $DG$.

But $E$ also divides the whole $DC$.

Therefore $E$ also divides the remainder $GC$.

But $CG$ divides $FH$.

Therefore $E$ also divides $FH$.

But $E$ also divides the whole $FA$.

Therefore $E$ also divides the remainder, that is, the unit $AH$.

But $E > 1$ so this is impossible.

Therefore, from Book VII Definition 12: Relatively Prime, $AB$ and $CD$ are relatively prime.

$\blacksquare$

Historical Note

This is Proposition 1 of Book VII of Euclid's The Elements.