$d\mid a,b \iff d\mid\gcd(a,b) \ $ [GCD Universal Property]

Question

I know that the definition of gcd of two numbers $ a, b $ is $G$ ,where

$G\mid a$, $\;G\mid b $ and

If $d\mid a$, $\;d\mid b $, then $ d\mid G.$

Now, using this how do I prove that in $\mathbb Z$, this definition coincides with the definition that $G$ is the GREATEST (w.r.t. usual ordering) common divisor?

So to prove that I write, say $G=dq+ r,\; 0\le r<d$. My aim is to show that $ r$ is $0$. So I have to construct some $G+x $ which is also a divisor of both $ a$ and $b$, to get a contradiction. How do I get $ x$?

Answer 1

The definition says that the gcd $G$ 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) = ia\!+\!jb,\, $ 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".

Remark $\ $ Dually we have the universal property of LCM

Lemma $\ \ \ a,b\mid m\iff [a,b]\mid m\ \ \ $ [LCM Universal Property]