If $\gcd(a,b) = 1$ then $\gcd(a,a + b) = 1$

Question

Let $a$ and $b$ be integers. Show that if $(a,b) = 1$ then $(a,a + b) = 1$.

I'm stuck on how to do this proof. I tried using the fact that $ax+by=1$ but that didn't seem to help.

Answer 1

Suppose $\gcd(a,a+b) = d$. Then $d|a, d|a+b$. Since $d|a+b$ and $d|a$, it follows that $d|b$. So $d|a$ and $d|b$ meaning that $\gcd(a,b)|d$ (by definition of gcd). But $\gcd(a,b) = 1$ so $d = 1$.

Answer 2

Hint $\ $ If $\ d\mid a\ $ then $\,d\mid a+b\iff d\mid b.\,$ Thus $\,a,\,a+b\,$ and $\,a,b\,$ have the same set $\,S\,$ of common divisors $\,d,\,$ so they have the same greatest common divisor $(= \max\, S).$

Remark $\ $ Recall that $\ \gcd(a,a+b) = \gcd(a,b)\ $ is the descent step in the subtractive form of the Euclidean algorithm.

Answer 3

The answers by Sandeep Silwal and Bill Dubuque are much better. However, we can use the fact that $c$ and $d$ are relatively prime if and only if there exist integers $s$ and $t$ such that $cs+dt=1$.

Since $\gcd(a,b)=1$, there exist integers $x$ and $y$ such that $ax+by=1$.

It follows that $a(x-y)+(a+b)(y)=1$, and we conclude that $\gcd(a,a+b)=1$.