# Thread: need help on this discrete problem

1. ## need help on this discrete problem

gcd(a,b)=1 if and only if gcd(a,a+b)=1

prove.....

2. suppose gcd (a,b) = k.
k|a and k|b => k|(a+b)
So $\gcd (a,a+b) \geq k$ since k is a common divisor.
So if $\gcd (a,b) \not = 1$ then $\gcd (a,a+b) \not = 1$
Taking the contrapositive gives us gcd (a, a+b) = 1 => gcd (a,b) = 1

suppose gcd (a, a+b) = p. Then the proof for this direction is very very similar to the previous direction.

3. alright that makes sense thanks a lot for the help.