3
$\begingroup$

This question already has an answer here:

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.

$\endgroup$

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

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

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'$.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – anto.1501 Mar 10 '14 at 0:19
2
$\begingroup$

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).$

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.