Properties of GCD

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?

Related Linear and Abstract Algebra News on Phys.org

mathwonk

Homework Helper
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

Staff Emeritus
Gold Member
You get several different answers ? Show your examples.

One more thing : try working backwards...

Last edited:

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

Homework Helper
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

Homework Helper
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

Homework Helper
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

Homework Helper
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
Gold Member
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..."

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

Staff Emeritus
Gold Member
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

Homework Helper
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.

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