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

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

$A = C \times D$
$B = C \times E$
$D : E = A : B$

So $D$ and $E$ are in the same ratio with $A$ and $B$.

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