Number Theory GCD Question

In summary: For example, if x = y, then a and b are both 1, so d | (a+b)x = d | (a-b)x = 1, and your gcd will be 1. If x = 2y, then a and b are both -1, so d | (a+b)x = d | (a-b)x = -1, and your gcd will be -1. If x = 3y, then a and b are both 0, so d | (a+b)x = d | (a-b)x = 0, and your gcd will be 0. Hopefully this gives you some ideas to get started. In summary,
  • #1
PsychonautQQ
784
10

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 each other 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.
 
Physics news on Phys.org
  • #2
PsychonautQQ said:

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 each other 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
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

1. What is the definition of GCD in Number Theory?

The GCD (Greatest Common Divisor) in Number Theory refers to the largest positive integer that divides two or more numbers without leaving a remainder.

2. How is GCD calculated?

The GCD can be calculated using the Euclidean algorithm, which involves finding the remainder when dividing the larger number by the smaller number and repeating the process until the remainder is equal to 0. The last non-zero remainder is the GCD.

3. What is the relationship between GCD and prime numbers?

Prime numbers have a GCD of 1 with all other numbers, meaning they have no common factors except for 1. This is because prime numbers only have two factors, 1 and itself, so they cannot share any common factors with other numbers.

4. Can GCD be negative?

No, GCD is always a positive number. This is because it is the largest positive integer that divides two or more numbers without leaving a remainder.

5. What is the significance of GCD in Number Theory?

GCD is an important concept in Number Theory as it helps in simplifying fractions, finding common factors, and solving problems related to divisibility. It also has applications in cryptography, computer algorithms, and other areas of mathematics.

Similar threads

  • Calculus and Beyond Homework Help
Replies
4
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
820
  • Calculus and Beyond Homework Help
Replies
1
Views
798
  • Calculus and Beyond Homework Help
Replies
5
Views
1K
  • Calculus and Beyond Homework Help
Replies
4
Views
935
Replies
0
Views
402
  • Calculus and Beyond Homework Help
Replies
14
Views
397
  • Calculus and Beyond Homework Help
Replies
6
Views
1K
  • Linear and Abstract Algebra
Replies
8
Views
842
Back
Top