Number Theory GCD Question

  • #1
784
11

Homework Statement


Show that gcd(a+b,a-b) is either 1 or 2. (hint, show that d|2a and d|2b)

Homework Equations


d = x(a+b)+y(a-b)

The Attempt at a Solution


so by the definition of divisibility:
a+b = dr
a-b = ds

adding and subtracting these equalities from eachother we can arrive at where the hint wanted us to conclude:
(r+s) = 2a/d
(r-s) = 2b/d

Trying to figure out what to do from here, having a hard time using the hint to restrict d to 1 or 2.
 

Answers and Replies

  • #2
Dick
Science Advisor
Homework Helper
26,258
619

Homework Statement


Show that gcd(a+b,a-b) is either 1 or 2. (hint, show that d|2a and d|2b)

Homework Equations


d = x(a+b)+y(a-b)

The Attempt at a Solution


so by the definition of divisibility:
a+b = dr
a-b = ds

adding and subtracting these equalities from eachother we can arrive at where the hint wanted us to conclude:
(r+s) = 2a/d
(r-s) = 2b/d

Trying to figure out what to do from here, having a hard time using the hint to restrict d to 1 or 2.
You must have some condition on a and b. Like, are they relatively prime?
 
  • Like
Likes PsychonautQQ
  • #3
107
13
Hey there,

I think a really important concept that you might be forgetting is the principle of linearity with divisibility. Since your gcd divides both a+b and a-b, it is then also true that your gcd will divide ANY linear combination of these integers (assuming integer weights, of course).

Namely, instead of being completely general with divisibility, realize that you can manipulate the variables x and y in the expression d | (a+b)x + (a-b)y to get a form that is equally valid. I think that your book wants you to assume that a and b are coprime integers, as well.

So, why not try playing around and actually picking numerical values for x and y that can help eliminate either a or b?
 
  • Like
Likes PsychonautQQ

Related Threads on Number Theory GCD Question

  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
1
Views
972
Replies
5
Views
510
  • Last Post
Replies
4
Views
3K
  • Last Post
Replies
14
Views
2K
  • Last Post
Replies
1
Views
409
  • Last Post
Replies
2
Views
3K
Replies
2
Views
3K
  • Last Post
Replies
4
Views
40K
  • Last Post
Replies
1
Views
1K
Top