Prove gcd(a,b) = gcd(a+c,b) given b|c

Question

I think I'm on the right track, but I just don't know how to put it all together.

Also $ b\neq 0 $

I have the following:

If $ b|c $ , then $a + c = a + bq, q \in \mathbb Z$

If the $\gcd(a,b)$, say $d$, divides $a$ and $b$

Then $ d|bq $ and hence $ d | a + bq$

Thus $d | a+c$

The problem is I don't know how to show $d$ is the $\gcd(a +c, b)$ even though I know it divides both of them. Can someone help me with this?

Answer 1

As $b\mid c$, you have $c=bq$ for some $q \in \mathbb Z$ and hence, as by the euclidean algorithm you know $(a,b)=(a+b,b)=(a+2b,b),\cdots , (a+bk,b)$ for all $k\in \mathbb Z$ by a simple induction, and choose $k=q$ to obtain $(a,b)=(a+qb,b)=(a+c,b)$

Answer 2

Say $c=rb$. Then $$\begin{align*} x|a+c,b &\iff x|a+rb,b\\ &\iff x|a,b \end{align*}$$ So $a+c$ and $b$ have the same common divisors as $a$ and $b$.

Answer 3

To prove that $\ d=gcd (a+c,b)$ let $\ e$ be any common divisor of $\ a+c$ and $\ b$.
Also we have in hand that $\ c=bp$ for some $\ p\in\mathbb{Z}$ and $\ d = au+bv$ for some $\ u,v\in\mathbb{Z}$, by g.c.d algorithm.
Now \begin{align} e|a+c \;\text{and}\; e|b &\implies e|(a+c)x+by \forall x,y\in\mathbb{Z}\\ &\implies e|(a+bp)x+by \forall x,y\in\mathbb{Z}\\ &\implies e|ax+b(px+y) \forall x,y\in\mathbb{Z}\\ &\implies e|d , \; \text{putting}\; x=u\; \text{and}\; px+y=v\\ \end{align}

Thus $\ d|a+c$, $\ d|b$ and if any integer $\ e$ be a common divisor of $\ a+c$ and $\ b$ implies $\ e|d$.
Thus $\ d=gcd(a+c,b)$