Divisor of Sum of Coprime Integers

From ProofWiki
Jump to: navigation, search

Theorem

Let $a, b, c \in \Z_{>0}$ such that:

$a \perp b$ and $c \divides \paren {a + b}$.

where:

$a \perp b$ denotes $a$ and $b$ are coprime
$c \divides \paren {a + b}$ denotes that $c$ is a divisor of $a + b$.


Then $a \perp c$ and $b \perp c$.


That is, a divisor of the sum of two coprime integers is coprime to both.


Proof

Let $d \in \Z_{>0}: d \divides c \land d \divides a$.

Then:

\(\displaystyle d\) \(\divides\) \(\displaystyle \paren {a + b}\) as $c \divides \paren {a + b}$
\(\displaystyle \leadsto \ \ \) \(\displaystyle d\) \(\divides\) \(\displaystyle \paren {a + b - a}\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle d\) \(\divides\) \(\displaystyle b\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle d\) \(=\) \(\displaystyle 1\) as $d \divides a$ and $d \divides b$ which are coprime


A similar argument shows that if $d \divides c \land d \divides b$ then $d \divides a$.

It follows that:

$\gcd \set {a, c} = \gcd \set {b, c} = 1$

Hence the result.

$\blacksquare$


Sources