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

AI Thread Summary
The discussion focuses on proving properties of the greatest common divisor (GCD) under specific conditions. It presents two problems: first, proving that if GCD(a,b) = 1, then GCD(a+b, a-b) equals either 1 or 2. The second problem involves proving that if GCD(a,b) = 1, then GCD(2a+b, a+2b) equals either 1 or 3. A key approach involves showing that the GCD of combinations of a and b can be derived from their linear combinations. The thread emphasizes the importance of identifying common factors and their implications on the GCD results.
ssome help
Messages
3
Reaction score
0
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.
 
Physics news on Phys.org
ssome help said:
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.
 
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.
 
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$
 
Back
Top