# GCD of Sum and Difference of Integers

Jump to navigation Jump to search

## Theorem

$\gcd \set {a + b, a - b} \ge \gcd \set {a, b}$

## Proof

Let $d = \gcd \set {a, b}$.

Then by definition of greatest common divisor:

$d \divides a \land d \divides b$
$d \divides \paren {a + b} \land d \divides \paren {a - b}$

By definition of common divisor:

$d \divides \gcd \set {a + b, a - b}$
$d \le \gcd \set{a + b, a - b}$

$\blacksquare$