Greatest Common Measure of Commensurable Magnitudes

Theorem

In the words of Euclid:

Given two commensurable magnitudes, to find their greatest common measure.

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

Porism

In the words of Euclid:

From this it is manifest that, if a magnitude measure two magnitudes, it will also measure their greatest common measure.

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

Proof

Let $AB$ and $CD$ be two commensurable magnitudes such that $AB < CD$.

$AB$ either measures $CD$ or it does not.

Let $AB$ measure $CD$.

As $AB$ also measures itself, it follows that $AB$ is a common measure for $AB$ and $CD$.

As no magnitude can measure a smaller magnitude, it follows that $AB$ is the greatest common measure of $AB$ and $CD$.

Let $AB$ not measure $CD$.

Let the less be continually subtracted in turn from the greater.

We are given that $AB$ and $CD$ are commensurable.

From Incommensurable Magnitudes do not Terminate in Euclid's Algorithm, that which is left over will eventually measure the one before it.

Let $AB$ measure $ED$ and leave $EC$ less than $AB$.

Let $EC$ measure $FB$ and leave $AF$ less than $EC$.

Let $AF$ measure $CE$.

Since:

$AF$ measure $CE$

and:

$CE$ measure $FB$

it follows that:

$AF$ measure $FB$.

But $AF$ also measures itself.

Therefore $AF$ measures the whole of $AB$.

But $AB$ also measures $DE$.

Therefore $AF$ also measures $DE$.

But $AB$ also measures $CE$.

Therefore $AF$ also measures the whole of $CD$.

Therefore $AF$ is a common measure for $AB$ and $CD$.

Suppose there were some magnitude $G$ which is greater than $AF$ which is also a common measure for $AB$ and $CD$.

Since:

$G$ measures $AB$

and:

$AB$ measures $ED$

it follows that:

$G$ measures $ED$.

But $G$ also measures the whole of $CD$.

Therefore $G$ also measures the remainder $CE$.

But $CE$ measures $FB$.

Therefore $G$ also measures $FB$.

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

Therefore it also measures the remainder $AF$.

But $G$ is greater than $AF$, and so cannot measure it.

From this contradiction it follows that $G$ cannot be a common measure for $AB$ and $CD$.

That is, $AF$ is the greatest common measure of $AB$ and $CD$.

$\blacksquare$

Historical Note

This proof is Proposition $3$ 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