# 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

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