# Prove that if $\gcd(a,c)=1$ and $\gcd(b,c)=1$ then $\gcd(ab,c)=1$ [duplicate]

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.

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

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

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

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

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.

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

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

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

• Can you fix the formatting? – user99914 Jun 14 '15 at 9:04