1
$\begingroup$

If $gcd(a,b) = 1$ then is it true that $gcd(2a,2b) = 2$? More generally, if $gcd(a,b) = k$ then is it true that $gcd(an,bn) = n*gcd(a,b) = kn$?

Looking at Bézout's identity this seems to be the case since we could simply multiply both sides of the equation $ax + by = d$ by the constant $n$.

$\endgroup$
2
$\begingroup$

It is special case of the gcd distributive law $\ \gcd(na,nb)\, =\, n\gcd(a,b).\ $

See here for a few proofs of this law (by Bezout, universal property, and prime factorizations).

$\endgroup$
1
$\begingroup$

Let $n\ne 0$, and let $k=\gcd(a,b)$. It is not hard to see that $nk$ divides each of $na$ and $nb$.

Now we need to show that every common divisor of $na$ and $nb$ divides $nk$. Here we use the Bezout "Identity." There exist integers $s$ and $t$ such that $sa+tb=k$. Multiply through by $n$. We get $s(na)+t(nb)=nk$. From this we can see that any common divisor of $na$ and $nb$ divides $nk$.

Remark: The harder part of the argument was already in the OP.

$\endgroup$
  • $\begingroup$ This is the Bezout method I mention. In the link I highlight how it arises from the preservation under scalings of objects defined by linear equations and divisibility relations, i.e. by innate scaling symmetry. $\endgroup$ – Bill Dubuque Feb 12 '15 at 4:35
  • $\begingroup$ The link, and your earlier posts along similar lines, are very useful. $\endgroup$ – André Nicolas Feb 12 '15 at 4:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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