# GCD Discrete math

#### ssome help

##### New member
Given that GCD(na,nb) = n * GCD(a,b) for a,b,n ∈ Z+

a) Prove that, if GCD(a,b) = 1 then GCD(a+b, a-b) = 1 or GCD(a+b,a-b) = 2
Hint: Let D = GCD(a+b, a-b), show that D | 2a and D | 2b thus D | GCD(2a,2b) then use the given
b) Prove that, if GCD(a,B) = 1, then GCD(2a+b, a+2b) = 1 or GCD(2a+b, a+2b) = 3

Any assistance would be great.

#### Klaas van Aarsen

##### MHB Seeker
Staff member
Given that GCD(na,nb) = n * GCD(a,b) for a,b,n ∈ Z+

a) Prove that, if GCD(a,b) = 1 then GCD(a+b, a-b) = 1 or GCD(a+b,a-b) = 2
Hint: Let D = GCD(a+b, a-b), show that D | 2a and D | 2b thus D | GCD(2a,2b) then use the given
b) Prove that, if GCD(a,B) = 1, then GCD(2a+b, a+2b) = 1 or GCD(2a+b, a+2b) = 3

Any assistance would be great.
Welcome to MHB, ssome help!

Nice problem.

Did you try anything?
When you show something you tried, or if you explain where you are stuck, we can help you to solve and understand this.

#### Evgeny.Makarov

##### Well-known member
MHB Math Scholar
The key fact to use here is that if d | x and d | y, then d divides any linear combination of x and y, i.e., d | (mx + ny) for any integer m and n.

#### chisigma

##### Well-known member
Setting...

$\displaystyle x = a + b$

$\displaystyle y = a - b$ (1)

... solving (1) we obtain...

$\displaystyle a = \frac{x + y}{2}$

$\displaystyle b = \frac{x - y}{2}$ (2)

Now if x and y have a common factor different than 2, then x + y and x - y have the the same common factor and the same would be for a and b and that is a contradiction...

Kind regards

$\chi$ $\sigma$