# Product of Coprime Pairs is Coprime

## Theorem

Let $a, b, c, d$ be integers.

Let:

$a \perp c, b \perp c, a \perp d, b \perp d$

where $a \perp c$ denotes that $a$ and $c$ are coprime.

Then:

$a b \perp c d$

In the words of Euclid:

If two numbers be prime to two numbers, both to each, their products also will be prime to one another.

## Proof

Let $e = a b, f = c d$.

 $\ds a$ $\perp$ $\ds c$ $\ds \land \ \$ $\ds b$ $\perp$ $\ds c$ $\text {(1)}: \quad$ $\ds \implies \ \$ $\ds a b$ $\perp$ $\ds c$ Proposition $24$ of Book $\text{VII}$: Integer Coprime to Factors is Coprime to Whole $\ds a$ $\perp$ $\ds d$ $\ds \land \ \$ $\ds b$ $\perp$ $\ds d$ $\text {(2)}: \quad$ $\ds \implies \ \$ $\ds a b$ $\perp$ $\ds d$ Proposition $24$ of Book $\text{VII}$: Integer Coprime to Factors is Coprime to Whole $\ds a b$ $\perp$ $\ds c$ from $(1)$ $\ds \land \ \$ $\ds a b$ $\perp$ $\ds d$ from $(2)$ $\ds \implies \ \$ $\ds a b$ $\perp$ $\ds c d$ Proposition $24$ of Book $\text{VII}$: Integer Coprime to Factors is Coprime to Whole

$\blacksquare$

## Historical Note

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