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

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

$\blacksquare$

## Historical Note

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