Before defining the lcm I would like to prove following lemma about its properties:
Lemma If $a$ and $b$ are nonzero integers, then there is a unique positive integer $m$ such that
- $a,b\mid m$,
- $a,b\mid c\implies m\mid c$.
Proof Uniqueness: Suppose $m'$ is another such number, then from (2) follow $m\mid m'$ and $m'\mid m$, thus by Lemma ??? $|m|=|m'|$ and since both are positive, follows that $m=m'$.
Existence: We define $S=\{n\in\mathbb{N} : a,b\mid x\}$, since $|ab|\in S$, then $S\neq\varnothing$. Let $m$ be the minimum of the set (todo: existence from set theory), thus $a,b\mid m$, proving (1).
Now suppose $a,b\mid c$, set $d:=\gcd(a,b)$, then $$...$$ Conclusion $m\mid c$.
Is it possible to fill the dots using Bezout and the usual identities for divisors and gcd? Without primes and Division Algorithm (I think this is one of the standard way) and $\textrm{lcm}(a,b)\gcd(a,b)=ab$. If not, is there an explanation why not?
I tried starting from the second proof of this answer here, but I don't get anywhere.
EDIT
Completion of the proof based on the answer of @haran :
Now suppose $a,b\mid c$, set $d:=\gcd(a,b)$, then $a,b\mid m,c$, thus $a,b\mid \gcd(m,c)\le m$ (because $\gcd(a,b)\le a$). Thus $\gcd(m,c)\in S$, but since $m$ is the minimal element, $\gcd(m,c)=m$ and we can conclude that $m\mid c$.
The uniqueness proof as you have done above is straightforward and beautiful. For the proof of existence, first define LCM as the smallest number divisible by both inputs. We know that the product of two numbers is divisible by them individually which shows $lcm(a,b)<ab+1$.
Now it suffices to show that if there exists a number $x$ such that both the numbers divide, then the LCM which is $y$ divides it too. Assume the contrary, then since $a$ and $b$ divide both $x,y$, we have $a$ and $b$ divide $\gcd(x,y) =z$. Note that now, $z < y$ but this contradicts our definition of LCM being the smallest number divisible by both $a,b$.
Hence our initial assumption is false. Thus, the definition of LCM being the least number divisible by $a,b$ is the same as the definition given. Since we have already proved that if LCM is the least number divisible by $a,b$, then there exists and LCM for every $a$ and $b$, we are done!