suppose gcd (a,b) = k.

k|a and k|b => k|(a+b)

So since k is a common divisor.

So if then

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.