GCD Discrete Math: Proving GCD(a,b)=1

[ssome help]

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.

 

[I like Serena]

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]

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]

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$

 

[blue_raver22]

a) To prove that GCD(a+b, a-b) = 1 or GCD(a+b, a-b) = 2, we first let D = GCD(a+b, a-b). This means that D divides both a+b and a-b. Therefore, D also divides their sum and difference, which are 2a and 2b respectively.

Using the given property, GCD(na,nb) = n * GCD(a,b), we can write D | 2a and D | 2b as D | GCD(2a,2b). Since GCD(a,b) = 1, we know that GCD(2a,2b) = 2 * 1 = 2. Therefore, D must divide 2.

This means that D = 1 or D = 2, since these are the only positive divisors of 2. Therefore, we can conclude that GCD(a+b, a-b) = 1 or GCD(a+b, a-b) = 2.

b) Similarly, we let D = GCD(2a+b, a+2b). This means that D divides both 2a+b and a+2b. Therefore, D also divides their sum and difference, which are 3a and 3b respectively.

Using the given property, GCD(na,nb) = n * GCD(a,b), we can write D | 3a and D | 3b as D | GCD(3a,3b). Since GCD(a,b) = 1, we know that GCD(3a,3b) = 3 * 1 = 3. Therefore, D must divide 3.

This means that D = 1 or D = 3, since these are the only positive divisors of 3. Therefore, we can conclude that GCD(2a+b, a+2b) = 1 or GCD(2a+b, a+2b) = 3.