Odd Number Coprime to Number is also Coprime to its Double

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $a, b \in \Z$ be integers.

Let $a$ be odd.

Let:

$a \perp b$

where $\perp$ denotes coprimality.


Then:

$a \perp 2 b$


In the words of Euclid:

If an odd number be prime to any number, it will also be prime to the double of it.

(The Elements: Book $\text{IX}$: Proposition $31$)


Proof

By definition of odd number:

$a \perp 2$

The result follows from Integer Coprime to all Factors is Coprime to Whole.

$\blacksquare$


Historical Note

This proof is Proposition $31$ of Book $\text{IX}$ of Euclid's The Elements.


Sources