Prove that $\gcd(a, b) = \gcd(a, b + ma)$?

Question

How can I prove that $\gcd(a, b) = \gcd (a, b + ma)$?

I have tried this: let $g = \gcd(a, b)$, then $g \mid a$ and $g \mid b$. This means that $g \mid ax+by$. I don't know what to do next.

Thanks.

Answer 1

For positive integers $x, y$ if $x|y$ and $y|x$ then $x = y$, right? Because for positive integers $x | y$ implies $x ≤ y$.

Let $m ∈ ℤ$. Let $g' = \gcd (a,b+ma)$. Because $g$ divides both $a$ and $b$, it divides $b + ma$ as well. So it’s a common divisor of $a$ and $b+ma$ and therefore divides $g' = \gcd (a, b +ma)$.

Doing the same argument for $g'$ and $-m$, you get $g' | \gcd (a,b + ma - ma) = \gcd (a, b) = g$.

So $g | g'$ and $g' | g$ and therefore $g = g'$.

Answer 2

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