This question already has an answer here:

As stated in the title, the problem to prove is

Let $a,b,c \in \mathbb{Z}$. If $\gcd(a,c)=1=\gcd(b,c)$, then $\gcd(ab,c)=1$.

I think I've proved it, but I would like a second opinion. Here goes:


Suppose $\exists d \neq 1 \in \mathbb{Z}$ s.t $\gcd(ab,c)=d$. It follows then that $d|ab$ and $d|c$.

Now, if $d|a$ but not $b$, then since $d|c$, by linearity we have $d|\gcd(a,c)$. But $\gcd(a,c)=1$ so then $d=1$. The argument for $d|b$ is similar, resulting in $d=1$. Thus, since both cases lead us to $d=1$, we have a contradiction on our hands $\implies$ $ab$ and $c$ must be relatively prime $\implies \gcd(ab,c)=1$.


The question: was this a valid argument or do you think I should provide more?


marked as duplicate by Martin Sleziak, Cornman, YuiTo Cheng, Lee David Chung Lin, Lord Shark the Unknown May 4 at 6:44

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.


Your proof is not correct. You have implicitly assumed that if $d\mid ab$ then either $d\mid a$ or $d\mid b$. But this is not true: for example, $10\mid4\times25$, but $10\not\mid4$ and $10\not\mid25$.

It's a little difficult to say what you could do for a proof, since the basic facts of number theory can be proved in various orders and I don't know what you have done in your course. But here is one possibility.

I assume you have done the following theorem.

Let $s,t$ be integers. Then $\gcd(s,t)=1$ if and only if there exist integers $x,y$ such that $sx+ty=1$.

If you apply this to $a,c$ and also to $b,c$, you have $$ax+cy=1\quad\hbox{and}\quad bu+cv=1$$ for some integers $x,y,u,v$. Can you see how to use these equations to show that $$ab(\cdots)+c(\cdots)=1\ ,$$ where both sets of dots are integers?

Good luck!

  • $\begingroup$ Remark that the Bezout-based proof above can be done more generally using only basic gcd laws - see my answer. $\endgroup$ – Bill Dubuque Jul 23 '14 at 14:13
  • $\begingroup$ Yes I was able to eventually figure this out. When I had initally posted this, I was trying to find elegant, short ways to write proofs of these. This was one of my short attempts and needless to say, this one along with my others, we not very successful. It seems at my current stage, it's the longer way or the highway LOL. Though, using Bezout lemma isn't very long... $\endgroup$ – user146925 Aug 3 '14 at 2:55
  • $\begingroup$ I'm working on this same problem and need another hint. I follow up until this point. $\endgroup$ – Chris Feb 24 '15 at 20:33

If $\gcd(ab,c)>1$, You can assume $d$ is a prime factor of $\gcd(ab,c)$.

And if $d$ is a prime number and $d\mid ab$, either $d\mid a$ or $d\mid b$ is true.

Then you will get $\gcd(a,c)>1$ or $\gcd(b,c)$>1, which is not true.

Therefore $\gcd(ab,c)=1$.


The proof implicitly assumes $\,d\mid ab\,\Rightarrow\,d\mid a\,$ or $\,d\mid b,\,$ which is true iff $\,d = p\,$ is prime (or $1$). However, you can reduce the proof to this case, since if $\,ab,c\,$ have a common divisor $\,d> 1\,$ then they also have a common prime divisor: any prime divisor of $\,d.$

Below is a more general proof using basic gcd laws (distributive, commutative, associative). Your version of Euclid's Lemma is a special case, since $\ (b,c) = 1\,\Rightarrow\, (a,b,c) = 1.$

Theorem $\, \ (a,c)(b,c)\, =\, (ab,c)\,\ $ if $\,\ \color{#c00}{(a,b,c) = 1}$

$\!\!\begin{eqnarray}{\bf Proof}\qquad\, (a,c)(b,c) &=&\, (a(b,c),c(b,c))\\ &=&\, ((ab,ac),(cb,cc))\\ &=&\, (ab,ac,cb,cc)\\ &=&\, (ab,c\color{#c00}{(a,b,c)})\\ &=&\, (ab,c)\end{eqnarray}$

Remark $\ $ See also this answer for related proofs by Bezout, ideals, etc.


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