# Proving ${\rm gcd}(a,b)=1$, $a\mid c$ and $b\mid c$ implies $ab\mid c$ WITHOUT Euclid's or Bezout's lemma.

I want to show prove the following statement: For any $a,b,c\in\mathbb Z$, if $a,b$ are coprime and both $a$ and $b$ divide $c$, then $ab$ has to divide $c$ as well.

Before marking this as a duplicate - I've spent some time searching and I couldn't find an elementary proof that does not rely on Euclid's or Bezout's lemma.

My approach is as follows:

Since $b$ divides $c$, there exists an integer $k$, such that $kb=c$.

Since $a$ divides $c$, by identity it also divides $kb$.

I now want to show that assuming $a$ doesn't divide $kb$ implies the existence of a common divisor $d>1$ of $a$ and $b$, however, I'm walking in circles trying to prove this step.

I'm not 100% sure there's an easy way to prove it, but I'd appreciate any hint on how to prove the statement without using Euclid's or Bezout's lemma, just using the definition of divisibility

$x\mid y\ \Rightarrow\ \exists\ z\in\mathbb Z:zx=y$

and Euclidean division

$\forall\ x\in\mathbb Z,y\in\mathbb Z^\times\ \exists\ q\in\mathbb Z,r\in\{0,\ldots,y-1\}:x=qy+r$.

• It is a consequence of gauss lemma Nov 30 '15 at 22:28

Hint $\,d\mapsto ab/d\,$ bijects the common divisors $\,d\,$ of $\,a,b\,$ with the common multiples $\le ab.$ Being order-$\rm\color{#c00}{reversing}$, it maps the $\rm\color{#c00}{Greatest}$ common divisor to the $\rm\color{#c00}{Least}$ common multiple, i.e. $\,{\rm\color{#c00}{G}CD}(a,b)\mapsto ab/{\rm GCD}(a,b) = {\rm \color{#c00}{L }CM}(a,b).\,$

Let $v_p(x)$ be the exponent of a prime $p$ in the decomposition of $x$.

• $x \mid y$ iff $v_p(x) \le v_p(y)$ for all $p$.

• $\gcd(a,b)=1$ implies $v_p(ab) = v_p(a)$ or $v_b(p)$.

• $a \mid c$ implies $v_p(a) \le v_p(c)$

• $b \mid c$ implies $v_p(b) \le v_p(c)$

The result follows.