1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Mar 25, 2012 #1
    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. jcsd
  3. Mar 26, 2012 #2
    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.
     
  4. Mar 26, 2012 #3
    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.
     
  5. Mar 27, 2012 #4

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Prove GCD(a+b,a-b) = 1 or 2
  1. Proving Matrix B=A^-1 (Replies: 7)

Loading...