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

  • 1
    $\begingroup$ It is the gretatest common divisor w.r.t. the partial order $ x\prec y\iff x\mid y$. $\endgroup$ – Bernard Sep 14 at 11:17
  • $\begingroup$ Could you please elaborate? $\endgroup$ – timotheechalamet Sep 14 at 11:36
  • $\begingroup$ 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. $\endgroup$ – 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]


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.