elementary number theory - 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$?

Answer

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