# Prove GCD(a+b,a-b) = 1 or 2

1. Mar 25, 2012

### teroenza

1. The problem statement, all variables and given/known data
Given that GCD(a,b)=1 , i.e. they are relatively prime, show that the GCD(a+b,a-b) is 1 or 2.

2. Relevant equations
am+bn=1 , for some integer m,n.

3. The attempt at a solution
I tried using k(a+b)+L(a-b)=1 or 2, but got nowhere. So I said, if d is the common divisor of (a+b,a-b), d divides the sum or difference of the two.

(a+b)+(a-b)=2a

(a+b)-(a-b)=2b

so d divides either if these. 2 is a common factor between the sum and difference, so I initially thought 2 is then a common factor of (a+b,a-b). I have tried inserting numbers and this is incorrect for some pairs. For example (a,b)=(3,2), and correct for others (3,1). I am not seeing how to differentiate these two cases.

Thank you

2. Mar 26, 2012

### sunjin09

I think what you can say is if d>2, then in order for d to divide (2a,2b), d (odd d) or d/2 (even d) must divide (a,b), which is impossible, so d<=2.

3. Mar 26, 2012

### teroenza

I was able to get it by multiplying am+bn=1 by two, and saying that d then divides 2. 2 is prime, and thus d must be 1 or 2. This has not been verified by grading, but is what i am submitting.

4. Mar 27, 2012

### Hurkyl

Staff Emeritus
Your proof is close to correct; really all that's missing is correctly reflecting upon what you've done.

You've shown that, if d divides GCD(a+b,a-b), then d divides GCD(2a,2b) = 2. This is enough to answer the problem.

And because this was only an "if P then Q" type statement, you should expect the possibility that Q could be true, but P not.

If you want to go further and predict exactly when you get 1 and when you get 2, there are at least two things to try:
• Use the fact you already know the GCD is 1 or 2, and devise an alternate way to directly test if 2 is the case
• Try refining your argument -- the Euclidean algorithm is often useful for GCD problems, even when working with symbolic arguments instead of explicit numbers