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

Question

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.

Answer 1

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.

Answer 2

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.