Prove that for any integers a and b and c, gcd(a, b) = gcd(a + bc, a + b(c − 1))

Question

Please help me with this question

Prove that for any integers $a$ and $b$, $$\mathrm{gcd}(a, b) = \mathrm{gcd}(a + bc, a + b(c − 1))$$

I tried to prove it but I didn't understand the part of $b(c-1)$

let $d=\mathrm{gcd} (a,b)$

$h=\mathrm{gcd}(a,btac)$

since $d= \mathrm{gcd}(a,b)\implies d|a\:\text{and}\: d|b$ and then $$ \begin{split} d|b\:\text{ and }\:d|ac & \implies d|b+ac\\ d|a\:\text{ and }\:d|b +d|ac & \implies d|h \end{split} $$

Answer 1

I assume the question should also say "for any integer $c$".

Clearly $\gcd(a,b)\mid a+cb$, because it divides each term separately, and similarly $\gcd(a,b)\mid a+(c-1)b$, so $\gcd(a,b)\mid\gcd(a+cb,a+(c-1)b)$.

Conversely, $\gcd(a+cb,a+(c-1)b)\mid (a+cb)-(a+(c-1)b)=b$. It therefore also divides $cb$ and hence divides $a+cb-cb=a$. So $\gcd(a+cb,a+(c-1)b)\mid\gcd(a,b)$.

Answer 2

For all integers $m,n$, we have $\gcd(m,n) = \gcd(m,n-m)$. By induction, we also have $\gcd(m,n) = \gcd(m,n-km)$, for some integer $k$ (this is Euclidean algorithm). Using that, we have:

$$\gcd(a+bc,a+b(c-1)) = \gcd(a+bc, (a+bc)-(a+b(c-1))) = \gcd(a+bc,b) = \gcd(a,b).$$