# Prove that $\gcd(a, b) = \gcd(a, b + ma)$? [duplicate]

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.

## marked as duplicate by M. Vinay, Jonas Meyer, Jyrki LahtonenJun 30 '16 at 12:33

• $\mathrm{mcd}$ being the most great common divisor? – k.stm Mar 9 '14 at 23:49
• Sorry, I meant gcd = greatest common divisor. – anto.1501 Mar 9 '14 at 23:50

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'$.
• This is my reasoning for the $g'$ part: $g'=(a,b + ma)$ → $g'$|$a$ and $g'$|$b+ma$ → $g'$ |$xa + y(b+ma)$. If $x=-m$ and $y=1$, then $g'$|$b$. We have that $g'$|$a$ and $g'$|$b$, so $g'$|$(a,b)$. Is this correct? – anto.1501 Mar 10 '14 at 0:19
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).$