Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
up vote 4 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


Plugging in the first equation you get


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

share|cite|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|cite|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|cite|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|cite|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|cite|improve this answer
You might consider reading other answers before posting your own. – peoplepower Jan 28 '13 at 2:57

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

share|cite|improve this answer
Can you fix the formatting? – Arctic Char Jun 14 '15 at 9:04

Your Answer


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.