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

\(\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