Numbers are Coprime iff Sum is Coprime to Both

From ProofWiki
Jump to: navigation, search

Theorem

Let $a, b$ be integers.


Then:

$a \perp b \iff a \perp \left({a + b}\right)$

where $a \perp b$ denotes that $a$ and $b$ are coprime.


In the words of Euclid:

If two numbers be prime to one another, the sum will also be prime to each of them; and if the sum of two numbers be prime to any one them, the original numbers will also be prime to one another.

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


Proof

Necessary Condition

Let $a \perp b$.

Suppose $a + b$ is not coprime to $a$.

Then:

$\exists d \in \Z_{>1}: d \mathop \backslash a, d \mathop \backslash \left({a + b}\right)$

But then:

$d \mathop \backslash \left({\left({a + b}\right) - a}\right)$

and so:

$d \mathop \backslash b$

and so $a$ and $b$ are not coprime.

From this contradiction it follows that $a + b$ is coprime to $a$.

$\Box$


Sufficient Condition

Let $a + b$ be coprime to $a$.

Suppose $a$ is not coprime to $b$.

Then:

$\exists d \in \Z_{>1}: d \mathop \backslash a, d \mathop \backslash b$

and so:

$d \mathop \backslash \left({a + b}\right)$

and so $a$ and $\left({a + b}\right)$ are not coprime.

From this contradiction it follows that $a$ is coprime to $b$.

$\blacksquare$


Historical Note

This theorem is Proposition $28$ of Book $\text{VII}$ of Euclid's The Elements.


Sources