2
$\begingroup$

This question already has an answer here:

Prove that if $\gcd(a,c)=1$ and $\gcd(b,c)=1$ then $\gcd(ab,c)=1$. My attempt is let $\gcd(ab,c)=d$. Since $d \mid ab$ and $d \mid c$ , $d \mid (abt+cs)$ for some integers $s$ and $t$. Then by definition of divisibility, we have $$abt+cs=dk$$ for some integers $k$. Then I got stuck here.

$\endgroup$

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

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.

5
$\begingroup$

Hint 1: First approach. Assume by contradiction that $d \neq 1$. Pick some prime $p$ which divides $d$. Then $p\mid ab$ and $p\mid c$. Do you see the contradiction?

Hint 2: Second approach. You know that

$$ax+cy=1$$ $$bz+ct=1$$

For some positive integers.The second equation yields

$$abz+act=a$$

Plugging in the first equation you get

$$(abz+act)x+cy=1$$

But this implies that $\gcd(ab,c)=1$ (Why?)...

$\endgroup$
  • $\begingroup$ Since $(ab)(zx)+(c)(atx+y)=1$ , by Bezout Lemma, we have gcd(ab,c)=1 , correct ? $\endgroup$ – Idonknow Jan 28 '13 at 2:55
  • $\begingroup$ @Idonknow Exactly. You don't even have to recall the BL, since this is the trivial part of Bezout Lemma: if $d|ab,c$ then $d$ divides the LHS thus $d|1$. $\endgroup$ – N. S. Jan 28 '13 at 3:41
4
$\begingroup$

Using the fundamental theorem of arithmetic, if $a$ and $c$ are coprime then there is no common prime in their prime factorisations. The same goes for $b$ and $c$, and hence the same goes for $ab$ and $c$.

$\endgroup$
2
$\begingroup$

Theorem $\rm\qquad gcd(ab,c)\,|\,\gcd(a,c)\,gcd(b,c)$

$\begin{eqnarray}\rm{\bf Proof}\qquad\quad\ \ gcd(a,c) &=&\:\rm j\:a+m\:c \quad for\ some\,\ j,m\in \Bbb Z\ \ by\ Bezout\\ \rm gcd(b,c) &=&\:\rm k\:b+n\:c \quad for\ some\,\ k,n\in \Bbb Z\ \ by\ Bezout\\ \rm\ \ \Rightarrow\ \ gcd(a,c)\,gcd(b,c) &=&\:\rm jk\,\color{#C00}{ ab} + \color{#C00}c\,(\cdots)\ \ \ for\, \ \ (\cdots)\in \Bbb Z \end{eqnarray}$

Since $\rm\:gcd(ab,c)\,|\,\color{#C00}{ab,c},\:$ it divides the right-side of prior, so also the left. $\ $ QED

$\endgroup$
1
$\begingroup$

By the fundamental theorem of arithmetic, every integer greater than $1$ has a unique prime factorization, except for the order of the prime factors.

Now as gcd($a$, $c$) and gcd($b$, $c$) are both $1$, it is obvious that $a$ and $c$ have no common prime factors and $b$ and $c$ have no common prime factors. So $ab$ and $c$ can have no common prime factors. Hope this helps.

$\endgroup$
  • $\begingroup$ You might consider reading other answers before posting your own. $\endgroup$ – peoplepower Jan 28 '13 at 2:57
0
$\begingroup$

(I’m assuming that you don’t have the fundamental theorem of arithmetic available; if you do, the result is trivial, since $c$ has no prime factors in common with $a$ and $b$. I’m assuming that you do have the fundamental result that if $m\mid kn$ and $\gcd(m,k)=1$, then $m\mid n$.)

HINT: Suppose that $d\mid c$. Since $\gcd(c,a)=1$, we know that $\gcd(d,a)=1$. If $d\mid ab$, therefore, we can conclude that $d\mid b$, and hence ... ?

$\endgroup$
0
$\begingroup$

Since $$\gcd(a,c)=1=\gcd(b,c),$$ then there exists $m,m',n,n' \in \mathbb{Z}$ such that $$ma+nc=1=m'b+n'c.$$ Thus because \begin{align} 1&=1\times1 \\&=(ma+nc)\times(m'b+n'c)\\&=(m)(m')ab+(man'+nm'b+ncn')c, \end{align} with $mm',man'+nm'b+ncn'\in \mathbb{Z}$ hence we must have $\gcd(ab,c)=1$.

$\endgroup$
  • 1
    $\begingroup$ Can you fix the formatting? $\endgroup$ – user99914 Jun 14 '15 at 9:04

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