5
$\begingroup$

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

$\endgroup$
4
  • 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, 2019 at 11:17
  • $\begingroup$ Could you please elaborate? $\endgroup$
    – jimm
    Sep 14, 2019 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, 2019 at 11:46
  • $\begingroup$ Except for zero. $\endgroup$
    – DanielV
    Nov 30, 2021 at 1:11

1 Answer 1

0
$\begingroup$

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) = 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".

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 Bezout equation for gcds so the above proof of the gcd universal property fails. But instead use prime factorizations to prove the gcd universal property (then it boils down to the universal property of min & max on 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.

$\endgroup$

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.