Expert: Paul Klarreich - 9/14/2007

Question
how do you prove that the gcd(a,a+b)=d if and only if the gcd(a,b)=d.

Answer
Questioner:   Chukuu
Category:  Advanced Math
Private:  No
 
Subject:  Abstract Algebra
Question:  how do you prove that the gcd(a,a+b)=d if and only if the gcd(a,b)=d.
..................................
Hi, Chukuu,

[This is Number Theory, not Abstract Algebra, but...]

I think a proof goes along these lines:

[We already know, I hope, that any common divisor of two numbers will also divide their sum and their difference.]

Let  c  be any divisor of  a and a+b.  
Then  c | b, because  b =  a+b - a.  
If  c | a,b, then  c | gcd(a,b).

Let  e  be any divisor of  a  and  b.  
Then  e | a+b.  If  e | a,a+b,  e | gcd(a,a+b)

Therefore the common divisors of  a,a+b  are exactly the common divisors of a,b.  Therefore the gcd(a,a+b) and gcd(a,b) must be the same.