For every natural number $n$, $\gcd(an,bn)=n\gcd(a,b).$

Question

For every natural number I am trying to show that $n$, $\gcd(an,bn)=n\gcd(a,b).$

Here is my attempt. Put $d = \gcd(a,b)$; we can write $d=aT+bJ$, where $T$ adn $J$ are integers. Then as $d\mid a$ and $d\mid b$, we can write the equation as $dgT + dhJ$ and if we multiple it by $n$ then it becomes $dngT + dnhJ$ and the common part is $dn$ hence dn is the $\gcd$.

Answer 1

What is $d$? is it an arbitrary integer? Usually $d$ is the $\gcd(a,b)$.

If $d = \gcd(a,b) $, then it is clear how to prove the relation, isn't it?

finding the gcd of $an$ and $bn$ is not difficult if you know the gcd of $a$ and $b$.

Answer 2

$$ \begin{align} \gcd(an,bn) = dn \Rightarrow anx+bny = dn \Rightarrow ax+by = d \Rightarrow \gcd(a,b) = d \end{align} $$

Answer 3

Use the Euclide algorithm. Assume $a>b$.

$$ a = bq + r, 0\le r < b\implies \gcd(a,b )= \gcd(b,r) $$ now multiply by $n$:$$ na = nbq + nr, 0\le nr < nb\implies \gcd(na,nb )= \gcd(nb,nr) $$ So at every step of the Euclide algorithm, everything will be multiplied by $n$. Hence so will be the end result: $$ \gcd(na,nb) = n\gcd(a,b) $$

Answer 4

$d=\gcd(a,b)$ iff $a=da'$ and $'b=db'$ with $\gcd(a',b')=1$.

Then $na=nda'$ and $nb=ndb'$ implies $nd=\gcd(na,nb)$

Answer 5

It's not sufficient to show that you can write $nd$ as a linear combination of $na$ and $nb$. This just shows that $nd$ is a multiple of $\gcd(na,nb)$.

However, if $e=\gcd(na,nb)$ and $nd=ke$, you have, for some integers $X$ and $Y$, $$ e=naX+nbY $$ and so $$ ke=nd=nkaX+nkbY $$ which implies $$ d=k(aX+bY) $$ Since $aX+bY=hd$ for some $h$, you get $hk=1$ so $k=1$.

Note: the greatest common divisor is always supposed to be positive.