How can I prove that if $\gcd(a, b) = 1$, then $\gcd(ab, c) = \gcd(a, c) \times \gcd(b, c)$?

By eea there exists $ax+by=1$ from $\gcd(a,b)=1$ so a and be are co-primes there also exists $dk=a$ and $dj= b$ where $d=\gcd(a,b)=1$ this is all the information I have gathered from the question but I dont know how to approach and solve it. Can anyone help explain to me how to arrive at the answer? Thanks!

  • $\begingroup$ Hint: do you know the Fundamental Theorem of arithmetic? $\endgroup$
    – Josh Chen
    Jun 25 '14 at 1:35
  • $\begingroup$ I haven't learned that yet. =( $\endgroup$
    – James
    Jun 25 '14 at 1:36
  • $\begingroup$ Perhaps if you share how gcd is defined for you, we can help you better. $\endgroup$
    – vadim123
    Jun 25 '14 at 2:04

Without using primes. We show that $(ab,c) \mid (a,c)(b,c)$ and that $(a,c)(b,c)\mid (ab,c) $.

We have $ax+by=1$ multiplying by $c$ we have $acx+bcy=c$

Now $$(a,c)(b,c)\left[\frac{a}{(a,c)}\frac{c}{(b,c)}x+\frac{b}{(b,c)}\frac{c}{(a,c)}y\right]=c$$ where of course $\frac{a}{(a,c)}$ etc are integers. So $(a,c)(b,c)\mid c$. It is clear that $(a,c)(b,c)\mid ab$ since $(a,c)\mid a$ and $(b,c)\mid b$. And therefore we have $(a,c)(b,c)\mid (ab,c) $.

To show the other direction note that there are $p,q,r,s$ such that

$$ap+qc=(a,c)$$ and $$br+cs=(b,c)$$ thus $$(a,c)(b,c)=abpr +(aps+brq+qsc)c$$ and this latter is divisible by $(ab,c)$

  • $\begingroup$ Remark that Bezout is not needed, it is true in any gcd domain - see my answer. $\endgroup$ Jun 25 '14 at 2:31

Hint $\ $ By basic gcd laws (associative, commutative, distributive)

$\quad (a,c)(b,c) = (ab,ac,bc,cc) = (ab,\color{#c00}{(a,b,c)}c) = (ab,c),\,\ $ by $\ \,(a,b)=1\,\Rightarrow\,\color{#c00}{(a,b,c)=1}$


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.