Product of Coprime Pairs is Coprime
Jump to navigation
Jump to search
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$.
\(\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.
Sources
- 1926: Sir Thomas L. Heath: Euclid: The Thirteen Books of The Elements: Volume 2 (2nd ed.) ... (previous) ... (next): Book $\text{VII}$. Propositions