4
$\begingroup$

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

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

5 Answers 5

3
$\begingroup$

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

$\endgroup$
0
3
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ 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$. $\endgroup$ Oct 20, 2014 at 16:43
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .