Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

5 Answers 5

up vote 3 down vote accepted

Hint 1: First approach. Assume by contradiction that $d \neq 1$. Pick some prime $p$ which divides $d$. Then $p|ab$ and $p|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?)...

share|improve this answer
    
Since $(ab)(zx)+(c)(atx+y)=1$ , by Bezout Lemma, we have gcd(ab,c)=1 , correct ? –  Idonknow Jan 28 '13 at 2:55
    
@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$. –  N. S. Jan 28 '13 at 3:41

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

share|improve this answer

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

share|improve this answer

(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 ... ?

share|improve this answer

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.

share|improve this answer
    
You might consider reading other answers before posting your own. –  peoplepower Jan 28 '13 at 2:57

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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