Numbers forming Fraction in Lowest Terms are Coprime
Theorem
In the words of Euclid:
- The least numbers of those which have the same ratio with them are prime to one another.
(The Elements: Book $\text{VII}$: Proposition $22$)
Proof
Let $A, B$ be (natural) numbers which are the least of those which have the same ratio with them.
We need to show that $A$ and $B$ are prime to one another.
Aiming for a contradiction, suppose $A$ and $B$ are not coprime.
Then by definition there exists some (natural) number $C > 1$ which measures them both.
As many times as $C$ measures $A$, let that many units be in $D$.
As many times as $C$ measures $B$, let that many units be in $E$.
So by Book $\text{VII}$ Definition $15$: Multiply:
- $A = C \times D$
- $B = C \times E$
Thus by Proposition $17$ of Book $\text{VII} $: Multiples of Ratios of Numbers:
- $D : E = A : B$
So $D$ and $E$ are in the same ratio with $A$ and $B$.
But by Absolute Value of Integer is not less than Divisors: Corollary:
- $D < A$
- $E < B$
This contradicts our hypothesis that $A$ and $B$ are the least of those numbers that are in the same ratio with $A$ and $B$.
It follows that $A$ and $B$ must be prime to one another.
$\blacksquare$
Historical Note
This proof is Proposition $22$ of Book $\text{VII}$ of Euclid's The Elements.
It is the converse of Proposition $21$: Coprime Numbers form Fraction in Lowest Terms.
Sources
- 1926: Sir Thomas L. Heath: Euclid: The Thirteen Books of The Elements: Volume 2 (2nd ed.) ... (previous) ... (next): Book $\text{VII}$. Propositions