Relatively Prime Numbers proof

  • #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?
 

Answers and Replies

  • #2
AlephZero
Science Advisor
Homework Helper
6,994
292
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?
 
  • #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.
 

Related Threads on Relatively Prime Numbers proof

  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
5
Views
4K
  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
10
Views
3K
Replies
6
Views
758
  • Last Post
Replies
12
Views
1K
  • Last Post
Replies
2
Views
4K
  • Last Post
Replies
7
Views
988
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
5
Views
2K
Top