Incommensurable Magnitudes do not Terminate in Euclid's Algorithm

Theorem

In the words of Euclid:

If, when the less of two unequal magnitudes is continually subtracted in turn from the greater, that which is left never measures the one before it, the magnitudes will be incommensurable.

(The Elements: Book $\text{X}$: Proposition $2$)

Proof

Let $AB$ and $CD$ be unequal magnitudes such that $AB < CD$ which fulfil the condition of the statement.

Suppose $AB$ and $CD$ are commensurable magnitudes.

Then by definition some magnitude will measure them both.

Let $E$ be such a magnitude that measures both $AB$ and $CD$.

Let $AB$ measure $FD$ and leave $CF$ from $CD$.

Let $CF$ measure $BG$ and leave $AG$ from $AB$.

By hypothesis, this process can be repeated indefinitely.

Let it be repeated until some magnitude be left that is less than $E$.

Since:

$E$ measures $AB$

and:

$AB$ measures $DF$

then:

$E$ measures $FD$.

But $E$ also measures $CD$.

Therefore $E$ also measures $CF$.

But $CF$ measures $BG$.

Therefore $E$ also measures $BG$.

But $E$ also measures the whole of $AB$.

Therefore $E$ will also measures $AG$.

But $AG$ is less than $E$.

That means the greater magnitude measures the lesser magnitude.

From this contradiction it follows that no magnitude can measure both $AB$ and $CD$.

Therefore, by definition, $AB$ and $CD$ are incommensurable.

$\blacksquare$

Historical Note

This proof is Proposition $2$ of Book $\text{X}$ of Euclid's The Elements.

Sources

• 1926: Sir Thomas L. Heath: Euclid: The Thirteen Books of The Elements: Volume 3 (2nd ed.) ... (previous) ... (next): Book $\text{X}$. Propositions