Product of Coprime Pairs is Coprime

From ProofWiki
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