$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?

Solution 1:

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 "divisibly greatest" 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 $ $ "divides".

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 & 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>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 < \color{#90f}{a+b},\,$ so $\rm\color{}{induction}\,$ applies.

Solution 2:

First of all, it could be a definition. Otherwise, you may use the Euclidean algorithm and some elementary properties of division, or simply the unique prime factorisation of natural numbers.

Solution 3:

Use unique prime factorization: say $m=\displaystyle\prod_{i}{p_i}^{\alpha_i}$ and $n=\displaystyle\prod_i{p_i}^{\beta_i}$, then $\gcd(m,n)$ will contain the exponents $\min(\alpha_i,\beta_i)$.

Meanwhile, if $d$ has exponents $\delta_i$, then $d|m$ means exactly that each $\delta_i \le \alpha_i$. So, this is all a reformulation of the ($\delta_i\le\alpha_i$ and $\delta_i\le\beta_i$ then $\delta_i\le\min(\alpha_i,\beta_i)$) setting.