let $a,b$, and $c$ be integers with $b \ne 0$, and $b|c$. Prove that $\gcd(a,b) =\gcd(a+c, b)$

Question

since $( b|c)$, $c = xb$ So, $\gcd(a,b) = \gcd(a + xb, b)$ Euclidean algorithm shows shows that for $a=bq + r$, $\gcd(a,b) = \gcd(b,r)$ This is where im stuck, I've approached this quesiton so many ways but can't figure out how to apply the algorithm for the proof.

Answer 1

Suppose that $\gcd\;(a,b)=k$, then, $k|a$ and $k|b$. Clearly, $k|c$ as $b|c$. Now, this implies $k|(a+c)$ and $k|b$.

Now, we want to show if there exists an $m$ such that $m|(a+c)$ and $m|b$, then $m|k$, as $k$ is the $\gcd(a+c,b)$.

Now, $m|(a+c) \implies m|a$ and $m|b$, from this it shows that $m|\gcd(a,b)$. Hence $\gcd(a,b)=\gcd(a+c,b)$

Answer 2

Since $b \mid c$, $\exists k \in \mathbb Z$ such that $c=bk$. Now by Euclidean Algorithm, one always has $gcd(a,b)=gcd(a+bt,b)$ for any integer $t$. Now choose $k=t$.