# Product of Coprime Pairs is Coprime

Jump to navigation
Jump to search

## Contents

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

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

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

## Sources

- 1926: Sir Thomas L. Heath:
*Euclid: The Thirteen Books of The Elements: Volume 2*(2nd ed.) ... (previous) ... (next): Book $\text{VII}$. Propositions