GCD Properties: Find a+b & a-b

[cmurphy]

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]

note that if a prime numbers divides two other numbers then it also divides their sum.

 

[cmurphy]

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]

You get several different answers ? Show your examples.

One more thing : try working backwards...

 

[cmurphy]

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]

Have you found any cases where the answer is something other than gcd(a,b) or 2gcd(a,b)?

 

[TenaliRaman]

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

 

[cmurphy]

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]

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...?

 

[mathwonk]

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]

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]

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..."

 

[cmurphy]

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]

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.

 

[cmurphy]

No, not homework to turn in, just homework to know how to do so that I can work with the material.

 

[mathwonk]

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.