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.
I'm going to write $(m,n)$ for $\text{gcd}(m,n)$ throughout what follows.
You want to show that $(a,c)(b,c) \mid ab, c$. From the definition of $(m,n)$, it's easy to show that $(a,c)(b,c) \mid ab$ (since $(a,c) \mid a$ and $(b,c) \mid b$). So it really boils down to showing that $(a,c)(b,c) \mid c$.
Since $(a,c), (b,c) \mid c$, you can write $c = r(a,c) = s(b,c)$ for some integers $r$ and $s$. Therefore, to show that $(a,c)(b,c) \mid c$, it's enough to show that $(b,c) \mid r = c/(a,c)$. This is equivalent to showing that $p \nmid (a,c)$ for any prime number dividing $(b,c)$. This follows from $a$ and $b$ being coprime. (Why?)
Best Answer
Take a common divisor $k$ of $a$ and $b$. That means that we can write $a=ka'$, $b=kb'$. Then, if $d=ax+by$, $$d=a'kx+b'ky=k(a'x+b'y)$$ so we see that $k$ also divides $d$. Since $\gcd(a,b)$ is a common divisor of $a$ and $b$ (namely, the greatest), it also holds the property. Actually, the idea behind this is very simple: the sum of two multiples of the same number is also a multiple of the same number.
Note that $\gcd(a,b)$ is, hence, the least positive integer that can be written as $ax+by$, because every number of the form $ax+by$ must be a multiple of any common divisor of $a$ and $b$, and in particular, must be a multiple of $\gcd(a,b)$ so $ax+by$ can't be smaller than it (being still positive, of course).
Example: let $a=60$, $b=75$. The gcd is $15$, so $ax+by=60x+75y$ must be a multiple of $15$, because it is the sum of two multiples of $15$.
I hope this helps a bit.