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!

Relatively Prime Numbers proof

  1. Feb 13, 2007 #1
    1. Suppose that a and b are positive integers. Show that the following are equivalent: 1) a and b are relatively prime 2) a+b and b are relatively prime 3) a and a+b are relatively prime.



    2. I know that for a and b to be relatively prime, (a,b) = 1 (that is, their greatest common divisor is 1). Or, there exists an integer n such that if n divides a and n divides b, then n = +/-1.



    3. I'm starting by assuming that a and b are relatively prime. My problem is I don't know how to go about showing a+b and b are relatively prime (if I know how to show that, then "a and a+b are relatively prime" follows). This must be proof by cases, but where might I begin?
     
  2. jcsd
  3. Feb 13, 2007 #2

    AlephZero

    User Avatar
    Science Advisor
    Homework Helper

    Hint: supppose n is a factor of (a+b) and b.

    Then b = nx and a+b = ny for some integers x and y

    What does that tell you about the factors of a?
     
  4. Feb 13, 2007 #3
    The factors of a are n and y-x. This means that a, b, and a+b all have a common factor. Since a and b are relatively prime, the common factor must be 1.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Relatively Prime Numbers proof
  1. Prime number proof (Replies: 3)

Loading...