If $a \mid c$ and $b \mid c$, but $\gcd(a,b) = 1$, then $ab \mid c$.

Question

If $a | c$ and $b | c$ and $a$ and $b$ are relatively prime prove that $ab|c$.

What I did was since $(a,b)=1$ then we can find integers $m,n$ such that $ma + nb=1$. Now since $a|c$ then $a = mc$. Similary, since $b|c$ then $b=nc$. Then I got that:

$$ma+nb=1$$ $$c(m+n)=1$$ $$m +n = 1/c$$ $$abm +abn=\frac{ab}{c}.$$

Is this correct?

Answer 1

This is a special case of the Chinese Remainder Theorem. We know $$c \equiv 0 \pmod a$$ and $$c \equiv 0 \pmod b$$ and $\gcd(a,b)=1$. Hence the Chinese Remainder Theorem implies $$c \equiv 0 \pmod {ab}.$$

This is the relevant line from the Wikipedia link:

Hence $x \equiv y \pmod {n_i}$ for all $1 \leq i \leq k$, if and only if $x \equiv y \pmod N$.

Where $\{n_i\}_{i=1}^k$ are a set of coprime positive integers and $N=\prod_{i=1}^k n_i$.

Answer 2

If you want to avoid prime factorization, try saying $c = kab + r$ with $0 \leq r < ab$. Then, because $a | c$ and $b|c$, we have that $a | r$ and $b | r$. Since $(a,b) = 1$, what can you say about $r$?

Answer 3

The key ideas are present in your proof.

We know that $a \mid c$ and $b \mid c$. As $a \mid c$, we have that $c = ak$ for some integer $k$. In this form, we see that $b \mid c = ak$, but $\gcd(a,b) = 1$. By the theorem below, we have that $b \mid k$, so that $k = b \ell$. Now $c = ak = ab\ell$, and now it's clear that $ab \mid c$.

Theorem

If $a \mid bc$ and $\gcd(a,b) = 1$, then $a \mid c$.

This can be proved from your application of Bezout's Theorem in your attempted solution. And in fact this is the content of this question and its answers.