Proof: By Euclid
(related to Proposition: 7.22: Numbers forming Fraction in Lowest Terms are Co-prime)
- For if they are not prime to one another then some number will measure them.
- Let it (so measure them), and let it be $C$.
- And as many times as $C$ measures $A$, so many units let there be in $D$.
- And as many times as $C$ measures $B$, so many units let there be in $E$.
- Since $C$ measures $A$ according to the units in $D$, $C$ has thus made $A$ (by) multiplying $D$ [Def. 7.15] .
- So, for the same (reasons), $C$ has also made $B$ (by) multiplying $E$.
- So the number $C$ has made $A$ and $B$ (by) multiplying the two numbers $D$ and $E$ (respectively).
- Thus, as $D$ is to $E$, so $A$ (is) to $B$ [Prop. 7.17].
- Thus, $D$ and $E$ are in the same ratio as $A$ and $B$, being less than them.
- The very thing is impossible.
- Thus, some number does not measure the numbers $A$ and $B$.
- Thus, $A$ and $B$ are prime to one another.
- (Which is) the very thing it was required to show.
Adapted from (subject to copyright, with kind permission)
- Fitzpatrick, Richard: Euclid's "Elements of Geometry"