number theory - Prove common divisors of $a,b$ divide $gcd(a,b)$ without Bezout, primes or guessing the form of the GCD

Every proof of this fact that I've seen relies on guessing a "formula" for the GCD first, such as "the smallest positive integer of the form $ax+by$" or $\frac{ab}{\text{lcm}(a,b)}$. Then one shows that the guess was indeed correct and proves the result. I don't find these proofs very intuitive and I would like to know if there's a simpler proof that doesn't involve guessing what the GCD looks like (this includes the fundamental theorem of arithmetic, which seems like overkill).

The proof should go like this:

The statement is trivially true for $1$ and $(a,b)$ itself. Let $(a,b)=d$. Suppose $\exists c$ such that $1, $c \mid a$ and $c \mid b$ but $c \not \mid d$. Since $c, we have $1 \le (c,d) < c$. Suppose $(c,d)=1$. Then $a=dk$ and $c \mid a$ imply $c \mid k$, hence $cd \mid a$. In the same way $cd \mid b$, a contradiction.

Now suppose $1<(c,d). Then $\frac{c}{(c,d)} > 1$. I would like to show that $\frac{cd}{(c,d)} \mid a$, but here I get stuck. Can it be done with my restrictions? If not, why?

EDIT:

So my original proof only used multiplicative properties of $\Bbb Z$, but I have learned that the very existence of the GCD requires additive properties as well. However, I've found a new proof that doesn't seem to use any additive properties (not even duality with LCM). I believe it is closer to what I was looking for. The reasoning behind this proof relies on additive properties of $\Bbb Z$, but they seem to disappear in my formal proof. What's going on here? How is this proof equivalent to other proofs?

Proof. Let $c$ be a common divisor of $a$ and $b$ ($a) but $c \not \mid d$.

Since $c \not \mid d$, we can't have $a=d$, so $a=kd$ for some $k>1$. Also $a=tc$, for some $t>k$. We have $kd=tc \implies c=\frac kt d$. Observe that $k \not \mid t$, otherwise $d=\frac tk c \implies c \mid d$. Let $v=(k,t)$; then $1 \le v < k$. Of course $(\frac kv, \frac tv)=1$.
Now, $$b=k'd=t'c=t' \frac kt d \implies k'=t' \frac kt= t' \frac{k/v}{t/v} \implies t/v \mid t'$$ But then $b= t' \frac kt d = t' \frac {k/v}{t/v} d=\frac {t'}{t/v} \left(\frac kv d \right)$. Also $a=kd=v \left( \frac kv d \right)$. This shows that $\frac kv d > d$ is a common divisor and completes the proof. $\square$

Note that $c \mid \frac kv d$ as well.

This proof is a formalization of the following hand-waving:

suppose that $a=4d=6c$. Then the respective times $d$ and $c$ are contained in any common multiple of $d$ and $c$ must always have a ratio of $2:3$. This means that there must be a factor of $2d$ (and therefore $3c$) in any common multiple. If, for example, $b=5d$, then $b=6c+d$. But $c \mid b$ and $c \mid 6c$ imply $c \mid d$. This is impossible, because $3c=2d \implies 3=2 \frac dc$, a contradiction. This situation arises every time there are two common divisors and neither divides the other.

Answer

This is not so much a direct answer to your question as an indication of how one of the standard approaches might naturally be motivated

Suppose $c|a$ and $c|b$ then $c|ha+kb$ for any integer choice of $h$ and $k$.

It is natural to constrain $c$ as much as possible, and we do this by taking the least positive value of $ha+kb$. Let's call this $f$, so we have $c|f$.

Now let's think about how this relates to $a$. We have $f\le a$ since $1a+0b=a$ and so we can divide $a$ by $f$ to get $a=mf+n$ with $0\le n\lt f\le a$. But $n=a-mf=(1-mh)a-mkb$ can't be a positive value, so must be zero. We therefore have $f|a$. Likewise $f|b$.

We now know that any common factor of $a$ and $b$ divides $f$, and also that $f$ is a common factor.

---

The tricky part of the proof, which you can do by uniqueness of prime factorisation as well, is to show that any common factor divides the highest common factor. Note that proving uniqueness of prime factorisation uses the additive properties of the integers and doesn't just depend on multiplicative properties.

So you will find that, at least implicit within your argument is an appeal to the additive properties of the integers.

This is quite a subtle point, and is the reason why the most efficient proofs are written the way they are. I agree they can seem a bit like magic, but they can also be motivated, as I have tried to illustrate.