3
$\begingroup$

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.

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

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.

$\endgroup$
4
  • $\begingroup$ Using the definition that $\gcd$ is the greatest common divisor, how do I show that $|n|$ divides $\gcd(an,bn)$? This part gets me. $\endgroup$ – nettle Sep 16 '15 at 5:48
  • 1
    $\begingroup$ 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)$. $\endgroup$ – Scientifica Sep 16 '15 at 12:27
  • $\begingroup$ 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. $\endgroup$ – nettle Sep 16 '15 at 19:18
  • $\begingroup$ 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. $\endgroup$ – Scientifica Sep 16 '15 at 19:42
2
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ 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)$? $\endgroup$ – Scientifica Sep 16 '15 at 12:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.