2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ It is a consequence of gauss lemma $\endgroup$ – Maman Nov 30 '15 at 22:28
1
$\begingroup$

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).\,$

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.