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

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

• It is the gretatest common divisor w.r.t. the partial order $x\prec y\iff x\mid y$. – Bernard Sep 14 at 11:17
• Could you please elaborate? – timotheechalamet Sep 14 at 11:36
• Well, by definition, $G\succ d$ for any common divisor of $a$ and $b$. Incidentally, $G\succ d$ implies $G\ge d$ for the usual ordering. I'm not sure this is what you had in mind with ‘elaborate’, though. – Bernard Sep 14 at 11:46

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]