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!

Homework Help: 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


    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook