$c\mid a,b\iff c\mid\gcd(a,b)$ [GCD Universal Property] If $c$ is a common divisor of $a$ and $b$ then $c$ divides the greatest common divisor of $a$ and $b$.  What can we use to prove this?
The general definition of a gcd $G$ is that it is a common divisor that is divisibly greatest, i.e. if $d$ is any common divisor then $\,d\mid G,\,$ so $\, d\le G,\,$ thus $G$ is  a greatest common divisor.  Combining both directions we obtain the following handy bidirectional form of the general definition of a gcd
$$g\,\text{ is a gcd of }\,a,b\,\text{ in }R\ \ \text{ if }\ \  \bbox[5px,border:1px solid #c00]{d\mid a,b\iff d\mid g}\ \text{ holds for all}\ \ d\in R\qquad\qquad\ \ \ \ \ \ \ \ $$
Indeed putting $\,d=g\,$ in $(\Leftarrow)$ yields $\,g\mid a,b,\,$ so $\,g\,$ is a common divisor of $\,a,b,\,$  and necessarily  divisibly greatest since direction $(\Rightarrow)$ shows every common divisor $\,d\,$ divides $\,g.$
Below is a proof of the &quot;divisibly greatest&quot; form of the gcd in $\Bbb Z,\,$ via Bezout.
Theorem $\ \ \ \   d\mid a,b\iff d\mid (a,b)\ \ \ $ [GCD Universal Property]
${\bf Proof}\ \ (\Rightarrow)\ \ \ d\mid a,b\,\Rightarrow\, d\mid (a,b) = i\,a+j\,b,\, $ some $\, i,j\in\Bbb Z,\,$ by Bezout.
$(\Leftarrow)\ \ \ \ d\mid (a,b)\mid a,b\,\Rightarrow\, d\mid a,b\ $ by transitivity of $ $ &quot;divides&quot;.
Note that the proof shows that a linear common divisor is always greatest, i.e. any common divisor $ \:d\:$ of $ \:a,b\:$ that is an integral linear combination of them $ \:d = i\,a + j\,b\:$ is necessarily the greatest common divisor, since, as above, every common divisor $ \:c\:$ divides $ \:d,\:$ hence $ \:c\le d.\,$ If we inline the linked Bezout proof here we obtain a direct proof by Euclidean descent (induction).
Remark  $\ $ Dually we have the universal property of LCM
Lemma $\ \ \ a,b\mid m\iff [a,b]\mid m\ \ \ $ [LCM Universal Property]
In more general UFD's such as $\,\Bbb Z[x]\,$ and $\,\Bbb Q[x,y]\,$ there generally is not a linear representation (Bezout equation) for gcds but we can instead use prime factorizations to prove the above properties (then these properties boil down to the universal propery of min &amp; max on the exponents of primes, e.g. see here).

Or we can prove the GCD Universal Property directly by induction on $\,\color{#90f}{{\rm size} := a\!+\!b}.\,$ It's clearly true if $\,a\!=\!0\,$ or $\,b\!=\!0,\,$ or if $\,a\! =\! b\!:\ c\mid a,a\!\iff\! c\mid (a,a)=a.\,$ Else $\,a\!\neq\! b\!\neq\!0.\,$ By symmetry, wlog $\,a&gt;b.\,$  so $\, c\mid a,b\!\iff\! \color{#0a0}{c\mid a\!-\!b,b}\!\iff\! c\mid(a\!-\!b,b)=(a,b)\,$ since  $\,\color{#0a0}{\rm green}\,$ instance has smaller $\,\color{#90f}{{\rm size}} = (a\!-\!b)+b = a &lt; \color{#90f}{a+b},\,$ so $\rm\color{}{induction}\,$ applies.
This can be shown based on what we are given by showing $a$ and $b$ in terms of a product of $c$. If $c$ is a common divisor of $a$ and $b$, that means a and b are each the product of at least one $c$ and another natural number: $a = c^np$ and $b=c^nq$, with $a,b,c,n,p,q \in \mathbb N$. There are then two possibilities:


Either $c$, or a power of $c$ $c^n$, is the GCD of $a$ and $b$. Trivially, $c$ divides any $c^n$ where $n&gt;0$.
Neither $c$  nor any $c^n$ is the GCD of $a$ and $b$; in that case, $p$ and $q$ have their own GCD $m &gt; 1$, and the GCD of $a$ and $b$ is $c^nm$; again, by inspection, we see that $c$ divides any $c^nm$ to produce $c^{n-1}m$.