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

Question

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.

Answer 1

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

Answer 2

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

Answer 3

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

Answer 4

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.

Answer 5

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