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
    Jun 25, 2014 at 1:35
  • $\begingroup$ I haven't learned that yet. =( $\endgroup$
    – James
    Jun 25, 2014 at 1:36
  • $\begingroup$ Perhaps if you share how gcd is defined for you, we can help you better. $\endgroup$
    – vadim123
    Jun 25, 2014 at 2:04

2 Answers 2


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, 2014 at 2:31

It is very easy: $ $by basic gcd laws (associative, commutative, distributive)

$$ (a,c)(b,c) = (ab,ac,bc,cc) = (ab,(\!\underbrace{{\color{#c00}{a,b}}}_{\color{#c00}{(a,\:\!b)\:\!=1}\!\!\!\!}\!,c)\:\!c) = (ab,c)\qquad\qquad$$

Remark $ $ This proof is more general than proofs using the Bezout equation for the gcd (e.g. other answer) since there are rings with gcds that don't satisfy a Bezout equation, e.g. the above proof still works in the polynomial rings $\,\Bbb Z[x]\,$ and $\,\Bbb Q[x,y]\,$ where Bezout fails (e.g. $\,x,y\,$ are coprime but $\, ax+by= 1\Rightarrow 0 = 1$ by eval at $\,x=0=y).$

  • $\begingroup$ Compare here. $\endgroup$ Nov 19, 2022 at 13:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .