How to prove $\gcd(a-bc, b) =\gcd(a,b)$ for $a,b,c \in \mathbb{Z}$? I'm not really sure how to approach the problem, since I'm not really sure I understand the mechanisms why it is true aside from putting some numbers in and see that it works.
Qualitatively, I'd try a proof by contradiction, trying to show that $\gcd(a-bc, b) \neq \gcd(a,b)$ and use some prime attribute to contradict the assumption.
 A: Let $d$ be a common divisor of $a-bc$ and $b$, then there exists integers $q_1$ and $q_2$ such that $a-bc=dq_2$ and $b=dq_1$. Hence $a-bc = a - (dq_1)c = dq_2$, thus $a=d(q_1c+q_2)$. It follows that $d$ is a common divisor of $a$ and $b$. 
Conversely, suppose that $d$ is a common divisor of $a$ and $b$, you have to show that $d$ is a common divisor of $a-bc$ and $b$.
A: Hint Try proving that each term of your equality divides the other, i.e.
$$\gcd(a-bc, b) | \gcd(a,b) \mbox{ and }   \gcd(a,b) |\gcd(a-bc, b)$$
A: The common divisors of $a$ and $b$ are the common divisors of $a-bc$ and $b$ and vice versa , because if $d|b$ then $d|a$ if and only if $d|a-bc$.
This immediately proves the claim.
A: Hint $\ $ If $\,d\mid b\ $ then $\ d\mid a\!-\!bc\iff d\mid a.\,$ Hence $\,a\!-\!bc,\,b\,$ and $\,a,b\,$ have the same set $S\,$ of common divisors $\,d,\,$ so they have the same greatest common divisor $(= \max\, S).$ 
A: This follows directly from the "Division Algorithm". Note that if 
$$
a=\overbrace{q}^{quotient}b+\overbrace{r}^{remainder},
$$ 
where $0\leq r<b$, then 
$$
a-bc=\overbrace{(q-c)}^{quotient}b+\overbrace{r}^{remainder}
$$
In other words, the remainder we get after dividing $a-bc$ by $b$ is the same as after dividing $a$ by $b$. Hence
$$
\gcd(a-bc,b)=\gcd(a,b)
$$
