# show that if $a | c$ and $b | c$, then $ab | c$ when $a$ is coprime to $b$.

Given two numbers $a$ and $b$, where $a$ is co-prime to $b$,

• Show that for any number $c$, if $a|c$ and $b | c$ then $ab| c$.
• Is the reverse also true? In other words, if $ab |c$ and $a$ is co-prime to $b$, then do we have $a | c$ as well as $b|c$?
-

The second property holds, but the assumption that $\gcd(a,b)=1$ is superfluous. In general, if $x|y$ and $y|z$, then $x|z$. Since $a|ab$ and $b|ab$, then $ab|c$ implies $a|c$ and $b|c$, without any conditions on $\gcd(a,b)$.

On the other hand, $\gcd(a,b)=1$ is required for the first.

There are a number of ways of doing the proof. One is to use the Bezout identity: for any integers $a$ and $b$, there exist integers $x$ and $y$ such that $\gcd(a,b)=ax+by$. If $\gcd(a,b)=1$, then we can write $1 = ax+by$. Multiplying through by $c$, we get $c=axc + byc$. Since $a|c$, we can write $c=ak$; and since $b|c$, we can write $c=b\ell$. So we have $$c = axc+byc = ax(b\ell) + by(ak) = ab(x\ell + yk),$$ so $ab|c$.

Another is to use the following property:

Lemma. If $a|xy$ and $\gcd(a,x)=1$, then $a|y$.

This can be done using the Bezout identity, but here is a proof that avoids it and only uses the properties of the gcd (so it is valid in a larger class of rings than Bezout rings): \begin{align*} r|\gcd(a,xy) & \iff r|a,xy\\ &\iff r|ay, xy,a\\ &\iff r|\gcd(ay,xy),a\\ &\iff r|y\gcd(a,x),a\\ &\iff r|y,a\\ &\iff r|\gcd(a,y) \end{align*} In particular, $a=\gcd(a,xy)$ divides $\gcd(a,y)$, which divides $y$, hence $a|y$.

With that Lemma on hand, we obtain that the result you want as follows: If $a|c$, then $c=ak$ for some $k$. Then $b|ak$, $\gcd(a,b)=1$. so $b|k$. Hence $k=b\ell$; thus, $c=ak=ab\ell$, so $ab|c$.

-
This is too small for an edit (for technical reasons), but you have a typo in "Since $a|c$, we can write $c=ba$", which should read "...$c=ak$". – Luke Mathieson Jul 21 '12 at 4:13
@Luke: Huh?${}{}{}$ – Arturo Magidin Jul 21 '12 at 4:14
Hopefully that makes sense now, typing on a real keyboard makes things a wee bit easier and less error prone. – Luke Mathieson Jul 21 '12 at 4:19
@Luke: Ah, gotcha. Yes, thank you. – Arturo Magidin Jul 21 '12 at 4:20

$\rm\, a\:|\:c\:\Rightarrow\:ab\:|\:bc\:\Rightarrow\: \color{#0A0}{\bf a}\:|\:\color{blue}{\bf b}\,(c/b)\color{#C00}\Rightarrow\, a\:|\:c/b\:\Rightarrow\:ab\:|\:c\ \,$ by $\rm\,\ (\color{#0A0}{\bf a},\color{blue}{\bf b})=1\,$ and $\rm\color{#C00}{Euclid's\ Lemma}$

The converse is easy: $\rm\:a\:|\:ab\:|\:c\:\Rightarrow\: a\:|\:c\:$ by transitivity of "divides".

-
Drat! Arturo beat me to it. – robjohn Jul 21 '12 at 3:16
@Rob But you have bigger Bezouka's. Ready, aim, fire! – Bill Dubuque Jul 21 '12 at 3:19