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

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

• What is the question here? Oct 20, 2014 at 16:38
• It might be easier to use the greatest common divisor version of $\gcd$, rather than the least linear combination version.
– user14972
Oct 20, 2014 at 16:59
• I still don't see any question mark.
– user147263
Oct 20, 2014 at 17:02

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

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

• I know, but look $d = aT + bJ$. Then as $d|a and d|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$. Oct 20, 2014 at 16:43

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

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

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.