Concise proof that every common divisor divides GCD without Bezout's identity? In the integers, it follows almost immediately from the division theorem and the fact that $a \mid x,y \implies a \mid 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\mid a,b \implies e\mid\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 \mid a,b$, then $e \mid \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 = \operatorname{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 \mid 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?

You might also use the fact that each natural number can be uniquely represented
as a product of prime powers to prove this fact without Bezout's Theorem.
This is called Fundamental Theorem of Arithmetic
For example  d=p1^d1*..*pn^dn where p1 to pn are primes.
The numbers p1 to pn are called then prime factors of d
Idea of the proof argument:
Since gcd(a,b) divides a and b each prime factor of gcd(a,b) has to be
a common prime factor of a and b.
For the same reason each prime factor of d has to be a common prime factor of
a and b.
And since gcd(a,b) is the greatest common divisor of a,b (by definition), each prime factor of d has to
be then a prime factor of gcd(a,b), for if there would be at least one prime factor p of
d which isn't a prime factor of gcd(a,b), then the product gcd(a,b)*p would be again
a common divisor of both a and b, greater than gcd(a,b), which would be a contradiction.
