If $\gcd(a,c)=1=\gcd(b,c)$, then $\gcd(ab,c)=1$

Question

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:

PROOF

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$.

$Q.E.D$

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

Answer 1

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!

Answer 2

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$.

Answer 3

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.