4
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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!

| cite | improve this answer | |
$\endgroup$
  • $\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
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

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