Euclidean Algorithm/Euclid's Proof

From ProofWiki
Jump to navigation Jump to search

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$.

Euclid-VII-2.png

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

Retrieved from "https://proofwiki.org/w/index.php?title=Euclidean_Algorithm/Euclid%27s_Proof&oldid=398930"