Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Properties of GCD

  1. Sep 18, 2004 #1
    I am trying to work through the following problem, and don't know where to start:

    I know that a, b are nonzero integers with gcd(a, b) = 1.

    I need to compute the gcd (a + b, a - b).

    Any help?
     
  2. jcsd
  3. Sep 18, 2004 #2

    mathwonk

    User Avatar
    Science Advisor
    Homework Helper
    2015 Award

    note that if a prime numbers divides two other numbers then it also divides their sum.
     
  4. Sep 18, 2004 #3
    Well, I understand that d | (a + b) and that d | (a - b), but I am not sure how to use this information to figure out the gcd of (a + b, a - b).

    I have tried it with just number examples, and I get different answers depending on the numbers that I choose, and I cannot figure out a relationship between the different examples.
     
  5. Sep 18, 2004 #4

    Gokul43201

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    You get several different answers ? Show your examples.

    One more thing : try working backwards...
     
    Last edited: Sep 18, 2004
  6. Sep 19, 2004 #5
    If I choose a = 3 and b = 11, then (a, b) = 1.
    Then (a+b, a-b) = (8, 14), so gcd = 2.

    But if I choose a = 2 and b = 7, then (a, b) = 1.
    Then (a+b, a-b) = (5, 9), so gcd = 1.
     
  7. Sep 19, 2004 #6

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Have you found any cases where the answer is something other than gcd(a,b) or 2gcd(a,b)?
     
  8. Sep 19, 2004 #7
    Decode this :p
    d = s(a+b)+t(a-b)
    d=(s+t)a+(s-t)b
    (s+t) & (s-t) both odd or even .... all OK
    but one of s+t or s-t odd/even ... not all OK
    so the d becomes?

    -- AI
     
  9. Sep 19, 2004 #8
    Ok, so if (s+t) and (s-t) are both even, then the gcd of them is 2.

    If one is even and one is odd, then the gcd is 1.

    This is a stupid question, I'm sure, but how do we know that s+t, s-t (if both even) cannot have a gcd > 2?
     
  10. Sep 19, 2004 #9

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    the gcd of x and y divides x+y and x-y.
    actually more is true: gcd(x,y)=gcd(x,y+x)=gcd(y,x+y)=gcd(x,y-x)=gcd(y,y-x)

    so let x=a+b, y=a-b and see that the gcd you're trying to calculate divides...?
     
    Last edited: Sep 19, 2004
  11. Sep 19, 2004 #10

    mathwonk

    User Avatar
    Science Advisor
    Homework Helper
    2015 Award

    you are using my hint backwards. the point is find what primes divides both a+b and a-b. so assume that p divides both of them, then it divides their sum.....
     
  12. Sep 19, 2004 #11

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    something i missed earlier:

    if one of s-t and s+t is even the other one must also be even, since their difference is even, so either they are both odd or both even, and not the cases you gave.
     
  13. Sep 19, 2004 #12

    Gokul43201

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    That's what I meant.

    I would recommend you simply do this...and in a couple of steps you have the required result.

    "Let p divide (a+b) and (a-b), then..."
     
  14. Sep 19, 2004 #13
    You would think that after all of these hints I would be closer to the proof. However, I now have several different pieces of information that I am unable to piece together.

    This is getting frustrating, because I know it's really easy!
     
  15. Sep 19, 2004 #14

    Gokul43201

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    I hope this isn't homework...

    This will not be rigorous..I leave that to you.

    Let p be a prime that divides (a+b) and (a-b).

    Then p must divide their sum and difference. So p|2a and p|2b

    And we know that there is no p that divides a and b, so either p must be 2 or the starting assumption was false.
     
  16. Sep 19, 2004 #15
    No, not homework to turn in, just homework to know how to do so that I can work with the material.
     
  17. Sep 23, 2004 #16

    mathwonk

    User Avatar
    Science Advisor
    Homework Helper
    2015 Award

    I am guessing that you are stuck thinking when you hear the words "sum of two numbers" that the sum must look like a+b. I.e. it did not occur to you that a symbol like a+b could be thought of as one number, so that "sum of two numbers" could be applied to the two numbers x = a+b and y = a-b.

    If so, then just realizing this, can help open your eyes to more possibilities in future.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Properties of GCD
  1. Gcd proof (Replies: 11)

  2. GCD question` (Replies: 3)

  3. GCD in PROOF? (Replies: 3)

  4. Gcd and lcm (Replies: 59)

  5. GCD question (Replies: 6)

Loading...