# Show that if a|c, b|c and gcd(a,b)=1, then ab|c

Let $a,b,c \in \mathbb{Z}$ such that $a|c$, $b|c$, gcd$(a,b)=1$. Prove that $ab|c$.

My thoughts so far: By the Unique Factorization Theorem, we can rewrite $a$ as $p_1^{\alpha_1}p_2^{\alpha_2}...p_k^{\alpha_k}$ where $p_i$'s are primes that make up $a$. Similarly, we can write $b=q_1^{\beta_1}q_2^{\beta_2}...q_k^{\beta_k}$, but with the restriction that $p_i\neq q_j$, $\forall i,j$. Then, by definition of "$|$," we can say that $a|c$ implies $\exists k \in \mathbb{Z}$ such that $k(p_1^{\alpha_1}p_2^{\alpha_2}...p_k^{\alpha_k})=c$. (Similarly for $b$).

From here I am unsure where to go, but it feels like I am only a lemma away from my conclusion.

• As a suggestion, try showing now: If $a \mid bc$, $\gcd(a, b) = 1$, then $a \mid c$. – cat Sep 14 '16 at 4:26

Any time you see $gcd(a,b)=1$, it can often be helpful to think of Bezout's identity. $$gcd(a,b)=1\Rightarrow \exists \; x,y\in\mathbb{Z}\;s.t\; 1=ax+by$$ Then we can scale to get $$c=cax+cby$$ And now using that $a\vert c,\;b\vert c \Rightarrow c=ak_1=bk_2$ our identity becomes $$c=cax+cby=axbk_2+aybk_1\Rightarrow c=ab(k_2x+k_1y)$$

• How did you eliminate $x$ and $y$? – Bobson Dugnutt Sep 13 '16 at 20:42
• I shouldnt have, I'll edit – qbert Sep 13 '16 at 20:46
• Then you should swap $k_1$ and $k_2$ in the last line (and you're still missing the $x,y$ in the middle equation). – Bobson Dugnutt Sep 13 '16 at 21:00
• fixed. next time I'll just put $k\in \mathbb{Z}$ asap – qbert Sep 13 '16 at 21:04

The idea is right. We can first add that it's not restrictive to assume $a,b,c>0$ (verify it).

Since $a\mid c$, we have $c=ak$; every prime power that divides $b$ must so divide $k$.

Alternatively, write $c=abq+r$, with $0\le r<ab$. Since $a\mid c$, we deduce that $a\mid r$ and, similarly, that $b\mid r$. Suppose $r>0$; then $r$ is a multiple of the lowest common multiple of $a$ and $b$, which is $ab$. Hence $r\ge ab$, a contradiction. Therefore $r=0$.

A quick way of going at it is using Gauss Lemma:

If $a$ and $b$ are coprime ($\gcd(a,b)=1$) then $a|bc\implies a|c$.

Reminder of the proof: By Bézout you have $u,v\in\mathbb{Z}$ such that $ua+vb=1$ and you just multiply by $c$ to see it through.

Now your exercice: $b|c$ so $c=bk$; $a|c$ implies by Gauss Lemma that $a|k$, so $ab|c$.

Since $a\mid c$ and $b\mid c$, we must have $\text{lcm}(a,b)\mid c$. We also have $ab=\gcd(a,b)\text{lcm}(a,b)$ and $\gcd(a,b)=1$, therefore $ab=\text{lcm}(a,b)$ and $ab\mid c$.

Since $a|c$ and $b | c$, there are $j, k$ such that $aj = c$ and $bk = c$.

Subce $gcd(a, b) = 1$, there are $u, v$ such that $au-bv = 1$.

$aju-bjv = j$ and $aku-bkv = k$ or $cu-bjv = j$ and $aku-cv = k$.

Once more, $acu-abjv = aj = c$ and $baku-bcv = bk = c$.

Adding these (because subtracting didn't do it), $2c =c(au-bv)-ab(ku-jv) =c-ab(ku-jv)$ or $c =ab(jv-ku)$ so $ab | c$.

Wadda ya know? I played around for a while and it worked!