Welcome to our community

Be a part of something great, join today!

GCD Discrete math

ssome help

New member
Apr 7, 2013
3
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
Mar 5, 2012
8,868
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
Jan 30, 2012
2,502
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
Feb 13, 2012
1,704
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$