Divisor of One of Coprime Numbers is Coprime to Other

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $a, b \in \N$ be numbers such that $a$ and $b$ are coprime:

$a \perp b$

Let $c > 1$ be a divisor of $a$:

$c \mathop \backslash a$

Then $c$ and $b$ are coprime:

$c \perp b$


In the words of Euclid:

If two numbers be prime to one another, the number which measures the one of them will be prime to the remaining number.

(The Elements: Book $\text{VII}$: Proposition $23$)


Proof 1

Let $a \perp b$ and $c > 1: c \mathop \backslash a$.

Suppose $c \not \perp b$.

So by definition of not coprime:

$\exists d > 1: d \mathop \backslash c, d \mathop \backslash b$.

But from Divisor Relation is Transitive:

$d \mathop \backslash c, c \mathop \backslash a \implies d \mathop \backslash a$

So $d$ is a common divisor of both $a$ and $b$.

So, by definition, $a$ and $b$ are not coprime.

The result follows by Proof by Contradiction.

$\blacksquare$


Proof 2

Let $A, B$ be two numbers which are prime to one another.

Let $C$ be any number greater than $1$ which measures $A$.

Euclid-VII-23.png

Suppose $C$ and $B$ are not prime to one another.

Then some number $D$ will measure them both.

We have that $D$ measures $C$ and $C$ measures $A$.

So $D$ measures $A$.

But $D$ also measures $B$.

So $D$ measures $A$ and $B$ which are prime to one another.

By Book $\text{VII}$ Definition $12$: Relatively Prime, this is a contradiction.

Therefore there can be no such $D$ that measures both $B$ and $C$.

That is, $B$ and $C$ are prime to one another.

$\blacksquare$


Historical Note

This theorem is Proposition $23$ of Book $\text{VII}$ of Euclid's The Elements.