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

[teroenza]

Homework Statement

Given that GCD(a,b)=1 , i.e. they are relatively prime, show that the GCD(a+b,a-b) is 1 or 2.

Homework Equations

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

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

 

[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.

 

[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.

 

[Hurkyl]

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