# Show that $\gcd(an,bn)=|n|\gcd(a,b)$

Show that $\gcd(an,bn)=|n|\gcd(a,b)$.

Question: Let $k=\gcd(a,b)$. Then $kq_1=a,kq_2=b$. Then $kq_1n=an,kq_2n=bn$. Hence, $kn|an$ and $kn|bn$. I'm having difficulty showing that, however, it's necessarily true that $kn=\gcd(an,bn)$.

I attempted proof by contradiction, i.e., suppose that there is an $r$ such that $r>kn$ and $r=\gcd(an,bn)$, but that gave me the trouble of showing that $r/n\in\mathbb Z$.

Note: One other similar question was submitted, but this is not the same. I want detailed clarification on the last bit.

• try proving gcd(q1,q2)=1 – JMP Sep 16 '15 at 5:26

The $\gcd$ of two numbers $p$ and $q$ is the positive integer that divides both of them and is divided by any common divisor of them.

You want to show that $k|n|=\gcd(an,bn)$ (you forgot the absolute value, but it's ok since in $\mathbb{Z}$ if $x$ divides $y$ then $|x|$ divides $y$). One way of doing that is to show that $k|n|$ divides $\gcd(an,bn)$ and $\gcd(an,bn)$ divides $k|n|$. You already proved one way because since $k|n|$ divides both $an$ and $bn$, it divides $\gcd(an,bn)$. Now try to prove that $\gcd(an,bn)$ divides $k|n|$. Notice that $|n|$ is a common divisor of $an$ and $bn$ thus $|n|$ divides $\gcd(an,bn)$ which proves that $\dfrac{\gcd(an,bn)}{n}\in\mathbb{Z}$ (this also shows why in your attempt you have $\dfrac{r}{n}\in\mathbb{Z}$). Then use the fact that $\gcd(an,bn)$ divides $an$ and $bn$ to conclude.

• Using the definition that $\gcd$ is the greatest common divisor, how do I show that $|n|$ divides $\gcd(an,bn)$? This part gets me. – nettle Sep 16 '15 at 5:48
• I didn't even try to find a proof using the definition because your problem is really easy using the proposition I mentioned in the answer:The $\gcd$ of two numbers $p$ and $q$ is the positive integer that divides both of them and is divided by any common divisor of them. It is clear that $|n|$ divides both $an$ and $bn$ right? Thus $|n|$ is a common divisor of $an$ and $bn$. As a result, $|n|$ divides $\gcd(an,bn)$. – Scientifica Sep 16 '15 at 12:27
• I needed a proof to justify that that $|n|$ divides $\gcd(an,bn)$, even if it was abundantly clear that $|n|$ divides $an$ and $bn$. Nonetheless, I worked one out using the Euclidean algorithm. So it's all good. Thanks for the help. – nettle Sep 16 '15 at 19:18
• Ah ok I missunderstood you. To prove that a common divisor of two numbers divides their $\gcd$ we have $\gcd(a,b)=ax+by$ for some $x,y\in\mathbb{Z}$. This is sometimes refered to as Euclidean algorithm so I guess that's what you used. No need to thank me, especially if I didn't answer you properly and in this case no need to accept my answer. – Scientifica Sep 16 '15 at 19:42

I think the simplest way to solve this problem is to note that if
$gcd(an,bn) = dn$, then $dn = anx + bny \therefore d = ax+by = gcd(a,b)$

Also note that if both $a$ and $b$ are negative (i.e. $n$ is negative) then the gcd is the same as if $a$ and $b$ were positive, i.e. $gcd(-a,-b) = gcd(a,b)$. The absolute value of $n$ should then be taken, as $|n|gcd(a,b) > ngcd(a,b)$ when $n$ is negative and the gcd should always be maximized.

• I agree that $\gcd(an,bn)=anx+bny$ where $a,b\in\mathbb{Z}$, but why $\gcd(a,b)=ax+by$? For sure $\exists u,v\in\mathbb{Z},\,\gcd(a,b)=au+bv$ but why would we have $(x,y)=(u,v)$? – Scientifica Sep 16 '15 at 12:30