Properties of GCD

  • Thread starter cmurphy
  • Start date
30
0
I am trying to work through the following problem, and don't know where to start:

I know that a, b are nonzero integers with gcd(a, b) = 1.

I need to compute the gcd (a + b, a - b).

Any help?
 

mathwonk

Science Advisor
Homework Helper
10,733
912
note that if a prime numbers divides two other numbers then it also divides their sum.
 
30
0
Well, I understand that d | (a + b) and that d | (a - b), but I am not sure how to use this information to figure out the gcd of (a + b, a - b).

I have tried it with just number examples, and I get different answers depending on the numbers that I choose, and I cannot figure out a relationship between the different examples.
 

Gokul43201

Staff Emeritus
Science Advisor
Gold Member
6,987
14
You get several different answers ? Show your examples.

One more thing : try working backwards...
 
Last edited:
30
0
If I choose a = 3 and b = 11, then (a, b) = 1.
Then (a+b, a-b) = (8, 14), so gcd = 2.

But if I choose a = 2 and b = 7, then (a, b) = 1.
Then (a+b, a-b) = (5, 9), so gcd = 1.
 

matt grime

Science Advisor
Homework Helper
9,394
3
Have you found any cases where the answer is something other than gcd(a,b) or 2gcd(a,b)?
 
644
1
Decode this :p
d = s(a+b)+t(a-b)
d=(s+t)a+(s-t)b
(s+t) & (s-t) both odd or even .... all OK
but one of s+t or s-t odd/even ... not all OK
so the d becomes?

-- AI
 
30
0
Ok, so if (s+t) and (s-t) are both even, then the gcd of them is 2.

If one is even and one is odd, then the gcd is 1.

This is a stupid question, I'm sure, but how do we know that s+t, s-t (if both even) cannot have a gcd > 2?
 

matt grime

Science Advisor
Homework Helper
9,394
3
the gcd of x and y divides x+y and x-y.
actually more is true: gcd(x,y)=gcd(x,y+x)=gcd(y,x+y)=gcd(x,y-x)=gcd(y,y-x)

so let x=a+b, y=a-b and see that the gcd you're trying to calculate divides...?
 
Last edited:

mathwonk

Science Advisor
Homework Helper
10,733
912
you are using my hint backwards. the point is find what primes divides both a+b and a-b. so assume that p divides both of them, then it divides their sum.....
 

matt grime

Science Advisor
Homework Helper
9,394
3
something i missed earlier:

if one of s-t and s+t is even the other one must also be even, since their difference is even, so either they are both odd or both even, and not the cases you gave.
 

Gokul43201

Staff Emeritus
Science Advisor
Gold Member
6,987
14
mathwonk said:
you are using my hint backwards. the point is find what primes divides both a+b and a-b. so assume that p divides both of them, then it divides their sum.....
That's what I meant.

I would recommend you simply do this...and in a couple of steps you have the required result.

"Let p divide (a+b) and (a-b), then..."
 
30
0
You would think that after all of these hints I would be closer to the proof. However, I now have several different pieces of information that I am unable to piece together.

This is getting frustrating, because I know it's really easy!
 

Gokul43201

Staff Emeritus
Science Advisor
Gold Member
6,987
14
I hope this isn't homework...

This will not be rigorous..I leave that to you.

Let p be a prime that divides (a+b) and (a-b).

Then p must divide their sum and difference. So p|2a and p|2b

And we know that there is no p that divides a and b, so either p must be 2 or the starting assumption was false.
 
30
0
No, not homework to turn in, just homework to know how to do so that I can work with the material.
 

mathwonk

Science Advisor
Homework Helper
10,733
912
I am guessing that you are stuck thinking when you hear the words "sum of two numbers" that the sum must look like a+b. I.e. it did not occur to you that a symbol like a+b could be thought of as one number, so that "sum of two numbers" could be applied to the two numbers x = a+b and y = a-b.

If so, then just realizing this, can help open your eyes to more possibilities in future.
 

Related Threads for: Properties of GCD

  • Posted
Replies
6
Views
4K
  • Posted
Replies
5
Views
3K
  • Posted
2 3
Replies
59
Views
11K
  • Posted
Replies
3
Views
2K
  • Posted
Replies
6
Views
4K
  • Posted
Replies
11
Views
3K
  • Posted
Replies
3
Views
2K
  • Posted
Replies
6
Views
2K

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving
Top