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$.
No comments:
Post a Comment