Let $a, b, c$ be integers. Prove that if $\gcd(a,b)=1$ then $\gcd(ab,c) = \gcd(a,c) \gcd(b,c)$
First time asking here. I'm not sure what your policies are on general homework help but I truly am stuck.
So far I have shown $\gcd(a,c) \gcd(b,c)$ as an integer combination of $ab$ and $c$. So if I can show that $\gcd(a,c) \gcd(b,c)$ divides $ab$ and $c$ I can use the proof that if an integer $d$ is a common divisor of $a$ and $b$, and $d=ax+by$ for some $x$ and $y$, that $d=\gcd(a,b)$. However I don't really know where to start with this. Any help would be appreciated.
Answer
I'm going to write $(m,n)$ for $\text{gcd}(m,n)$ throughout what follows.
You want to show that $(a,c)(b,c) \mid ab, c$. From the definition of $(m,n)$, it's easy to show that $(a,c)(b,c) \mid ab$ (since $(a,c) \mid a$ and $(b,c) \mid b$). So it really boils down to showing that $(a,c)(b,c) \mid c$.
Since $(a,c), (b,c) \mid c$, you can write $c = r(a,c) = s(b,c)$ for some integers $r$ and $s$. Therefore, to show that $(a,c)(b,c) \mid c$, it's enough to show that $(b,c) \mid r = c/(a,c)$. This is equivalent to showing that $p \nmid (a,c)$ for any prime number dividing $(b,c)$. This follows from $a$ and $b$ being coprime. (Why?)
No comments:
Post a Comment