1. Limited time only! Sign up for a free 30min personal 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!

Number Theory GCD Question

  1. Feb 13, 2015 #1
    1. The problem statement, all variables and given/known data
    Show that gcd(a+b,a-b) is either 1 or 2. (hint, show that d|2a and d|2b)

    2. Relevant equations
    d = x(a+b)+y(a-b)

    3. The attempt at a solution
    so by the definition of divisibility:
    a+b = dr
    a-b = ds

    adding and subtracting these equalities from eachother we can arrive at where the hint wanted us to conclude:
    (r+s) = 2a/d
    (r-s) = 2b/d

    Trying to figure out what to do from here, having a hard time using the hint to restrict d to 1 or 2.
     
  2. jcsd
  3. Feb 13, 2015 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    You must have some condition on a and b. Like, are they relatively prime?
     
  4. Feb 15, 2015 #3
    Hey there,

    I think a really important concept that you might be forgetting is the principle of linearity with divisibility. Since your gcd divides both a+b and a-b, it is then also true that your gcd will divide ANY linear combination of these integers (assuming integer weights, of course).

    Namely, instead of being completely general with divisibility, realize that you can manipulate the variables x and y in the expression d | (a+b)x + (a-b)y to get a form that is equally valid. I think that your book wants you to assume that a and b are coprime integers, as well.

    So, why not try playing around and actually picking numerical values for x and y that can help eliminate either a or b?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Number Theory GCD Question
Loading...