# Relatively Prime Numbers proof

• Black Orpheus

#### Black Orpheus

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?

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?

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.