GCD of Sum and Difference of Integers

From ProofWiki
Jump to navigation Jump to search


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


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

Then by definition of greatest common divisor:

$d \divides a \land d \divides b$

From Common Divisor Divides Integer Combination:

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

By definition of common divisor:

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

Hence from Absolute Value of Integer is not less than Divisors:

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