In the integers, it follows almost immediately from the division theorem and the fact that $a | x,y \implies a | ux + vy$ for any $u, v \in \mathbb{Z}$ that the least common multiple of $a$ and $b$ divides any other common multiple.
In contrast, proving $e|a,b \implies e|gcd(a,b)$ seems to be more difficult. In Elementary Number Theory by Jones & Jones, they do not try to prove this fact until establishing Bezout's identity. This Wikipedia page has a proof without Bezout's identity, but it is convoluted to my eyes.
I tried my hand at it, and what I got seems no cleaner:
Proposition: If $e | a,b$, then $e | gcd(a,b)$.
Proof: Let $d = gcd(a,b)$. Then if $e \nmid d$, by the division theorem there's some $q$ and $c$ such that $d = qe + c$ with $0 < c < r$.
We have $a = k_1 d$ and $b = k_2 d$, so by substituting we obtain $a = k_1 (qe + c)$ and $b = k_2 (qe + c)$. Since $e$ divides both $a$ and $b$, it must divide both $k_1 c$ and $k_2 c$ as well. This implies that both $k_1 c$ and $k_2 c$ are common multiples of $c$ and $r$.
Now let $l = lcm(r, c)$. $l$ divides both $k_1 c$ and $k_2 c$. Since $l = \phi c$ for some $\phi$, we have $\phi | k_1, k_2$, so $d \phi | a, b$.
But we must have $\phi > 1$ otherwise $l = c$, implying $r | c$, which could not be the case since $c < r$. So $d \phi$ is a common divisor greater than $d$, which is a contradiction. $\Box$
Question: Is there a cleaner proof I'm missing, or is this seemingly elementary proposition just not very easy to prove without using Bezout's identity?
Best Answer
One easy and insightful way is to use the proof below. It essentially constructs $\rm\:gcd\:$ from $\rm\:lcm\:$ by employing duality between minimal and maximal elements - see the Remark below. This is essentially how the linked Wikipedia proof works, but there the innate duality is obfuscated by the presentation. Below is a proof structured so that this fundamental duality is brought to the fore.
$\rm{\bf Theorem}\quad c\mid a,b\iff c\mid d,\ \ $ for $\rm\ \ d = ab/lcm(a,b).\ $ $\rm\color{#0a0}{Hence}$ $\rm\ d = gcd(a,b)$
$\rm{\bf Proof}\qquad\ \ \, c\mid a,b \iff a,b\mid ab/c \iff lcm(a,b)\mid ab/c \iff c\mid ab/lcm(a,b)$
$\rm\color{#0a0}{Generally}\,$ if $\rm\, c\mid a,b\iff c\mid d\ $ then $\rm\ d = \gcd(a,b)\ $ up to unit factors, i.e. they're associate.
Indeed setting $\rm\:c = d\:$ in direction $(\Leftarrow)$ shows that $\rm\:d\mid a,b,\:$ i.e. $\rm\:d\:$ is a common divisor of $\rm\:a,b.\:$ Conversely, by direction $(\Rightarrow)$ we deduce that $\rm\:d\:$ is divisible by every common divisor $\rm\:c\:$ of $\rm\:a,b,\:$ thus $\rm\:c\mid d\:\Rightarrow\: c\le d,\:$ so $\rm\:d\:$ is a greatest common divisor (both divisibility and magnitude-wise).
Remark $\ $ The proof shows that, in any domain, if $\rm\:lcm(a,b)\:$ exists then $\rm\:gcd(a,b)\:$ exists and $\rm\ gcd(a,b)\,lcm(a,b) = ab\ $ up to unit factors, i.e. they are associate. The innate duality in the proof is clarified by employing the involution $\rm\ x'\! = ab/x\ $ on the divisors of $\rm\:ab.\:$ Let's rewrite the proof using this involution (reflection).
Notice that $\rm\ x\,\mid\, y\:\color{#c00}\iff\: y'\mid x'\,\ $ by $\smash[t]{\,\ \rm\dfrac{y}x = \dfrac{x'}{y'} \ }$ by $\rm\, \ yy' = ab = xx',\ $ so rewriting using this
$\begin{eqnarray}\rm the\ proof\ \ \ c\mid a,b &\iff&\rm b,\,a\mid ab/c &\iff&\rm lcm(b,\,a)\mid ab/c &\iff&\rm c\mid ab/lcm(b,a)\\[.5em] \rm becomes\ \ \ \ c\mid a,b &\color{#c00}\iff&\rm a',b'\mid c' &\iff&\rm lcm(a',b')\mid c' &\color{#c00}\iff&\rm c\mid lcm(a',b')'\end{eqnarray}$
Now the innate duality is clear: $\rm\ gcd(a,b)\,=\,lcm(a',b')'\ $ by the $\rm\color{#0a0}{above}$ gcd characterization.