Proof: By Euclid
(related to Proposition: 7.24: Integer Co-prime to all Factors is Co-prime to Whole)
- For if $C$ and $D$ are not prime to one another then [some] number will measure $C$ and $D$.
- Let it (so) measure them, and let it be $E$.
- And since $C$ and $A$ are prime to one another, and some number $E$ measures $C$, $A$ and $E$ are thus prime to one another [Prop. 7.23].
- So as many times as $E$ measures $D$, so many units let there be in $F$.
- Thus, $F$ also measures $D$ according to the units in $E$ [Prop. 7.16].
- Thus, $E$ has made $D$ (by) multiplying $F$ [Def. 7.15] .
- But, in fact, $A$ has also made $D$ (by) multiplying $B$.
- Thus, the (number created) from (multiplying) $E$ and $F$ is equal to the (number created) from (multiplying) $A$ and $B$.
- And if the (rectangle contained) by the (two) outermost is equal to the (rectangle contained) by the middle (two) then the four numbers are proportional [Prop. 6.15].
- Thus, as $E$ is to $A$, so $B$ (is) to $F$.
- And $A$ and $E$ (are) prime (to one another).
- And (numbers) prime (to one another) are also the least (of those numbers having the same ratio) [Prop. 7.21].
- And the least numbers of those (numbers) having the same ratio measure those (numbers) having the same ratio as them an equal number of times, the greater (measuring) the greater, and the lesser the lesser - that is to say, the leading (measuring) the leading, and the following the following [Prop. 7.20].
- Thus, $E$ measures $B$.
- And it also measures $C$.
- Thus, $E$ measures $B$ and $C$, which are prime to one another.
- The very thing is impossible.
- Thus, some number cannot measure the numbers $C$ and $D$.
- Thus, $C$ and $D$ 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"