# Euclidean Algorithm/Euclid's Proof

## Theorem

In the words of Euclid:

*Given two (natural) numbers not prime to one another, to find their greatest common measure.*

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

## Proof

Let $AB, CD$ be the two given (natural) numbers which are not coprime.

We need to find the greatest common divisor of $AB$ and $CD$.

Without loss of generality that $CD \le AB$.

We have that $CD$ is a divisor of itself.

If $CD$ is a divisor of $AB$ then $CD$ is a common divisor of $CD$ and $AB$.

It is clearly the greatest, because no number greater than $CD$ can be a divisor of $CD$.

Now, suppose $CD$ does not divide $AB$.

Then the less of the numbers $AB, CD$ being continually subtracted from the greater, some number will be left which will be a divisor of the one before it.

From Coprimality Criterion, this number will not be a unit, otherwise $AB$ and $CD$ will be coprime.

So some number will be left which is a divisor of the one before it.

Now let $CD$, dividing $BE$, leave $EA$ less than itself.

Let $EA$, dividing $DF$, leave $FC$ less than itself.

Let $CF$ divide $AE$.

Since then $CF$ divides $AE$, and $AE$ divides $DF$, then $CF$ will also divide $DF$.

But it also divides itself.

Therefore it will also divide the whole $CD$.

But $CD$ divides $BE$, therefore $CF$ divides $BE$.

But it also divides $EA$, therefore it will also divide the whole $BA$.

So $CF$ is a common divisor of $CD$ and $AB$.

Suppose $CF$ is not the greatest common divisor of $CD$ and $AB$.

Let $G > CF$ also be a common divisor of $CD$ and $AB$.

Since $G$ divides $CD$, while $CD$ divides $BE$, it follows that $G$ divides $BE$.

But $G$ also divides the whole $BA$, and so it also divides the remainder $AE$.

But $AE$ divides $DF$.

Therefore $G$ divides $DF$.

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

Therefore it will also divide the remainder $CF$.

But $G$ is greater than $CF$, which is impossible.

Therefore no number greater than $CF$ divides the numbers $AB$ and $CD$.

Therefore $CF$ is the greatest common divisor of $AB$ and $CD$.

$\blacksquare$

## Porism

In the words of Euclid:

*From this it is manifest that, if a number measure two numbers, it will also measure their greatest common divisor.*

(*The Elements*: Book $\text{VII}$: Proposition $2$ : Porism)

## Historical Note

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

## Sources

- 1926: Sir Thomas L. Heath:
*Euclid: The Thirteen Books of The Elements: Volume 2*(2nd ed.) ... (previous) ... (next): Book $\text{VII}$. Propositions - 1971: Allan Clark:
*Elements of Abstract Algebra*... (previous) ... (next): Chapter $1$: Properties of the Natural Numbers: $\S 23 \zeta$ - 1992: George F. Simmons:
*Calculus Gems*... (previous) ... (next): Chapter $\text {A}.4$: Euclid (flourished ca. $300$ B.C.)