19
$\begingroup$

I have tried $\gcd(0,8)$ in a lot of online gcd (or hcf) calculators, but some say $\gcd(0,8)=0$, some other gives $\gcd(0,8)=8$ and some others give $\gcd(0,8)=1$. So really which one of these is correct and why there are different conventions?

$\endgroup$
23
$\begingroup$

Let's recall the definition of $ $ "$\rm a $ divides $\rm b$" $ $ in a ring $\rm\,Z,\, $ often written as $\rm\ a\mid b\ \ in\ Z.$

$\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad \rm\ a\mid b\ \ in\ Z\ \iff\ a\,c = b\ \ $ for some $\rm\ c\in Z$

Recall also the definition of $\rm\ gcd(a,b),\,$ namely

$(1)\rm\qquad\quad \rm gcd(a,b)\mid a,b\qquad\qquad\qquad\ $ the gcd is a common divisor

$(2)\rm\qquad\quad\! \rm c\mid a,b\ \ \ \Longrightarrow\ \ c\mid gcd(a,b)\quad$ the gcd is a greatest common divisor

$\ \ \ \ $ i.e. $\rm\quad\ c\mid a,b\ \iff\ c\mid gcd(a,b)\quad\,$ expressed in $\iff$ form $ $ [put $\rm\ c = gcd(a,b)\ $ for $(1)$]

Notice $\rm\quad\, c\mid a,0\ \iff\ c\mid a\,\ $ so $\rm\ gcd(a,0)\ =\ a\ $ by the prior "iff" form of the gcd definition.

Note that $\rm\ gcd(0,8) \ne 0\,$ since $\rm\ gcd(0,8) = 0\ \Rightarrow\ 0\mid 8\ $ contra $\rm\ 0\mid x\ \iff\ x = 0.$

Note that $\rm\ gcd(0,8) \ne 1\,$ else $\rm\ 8\mid 0,8\ \Rightarrow\ 8\mid gcd(0,8) = 1\ \Rightarrow\ 1/8 \in \mathbb Z. $

Therefore it makes no sense to define $\rm\ gcd(0,8)\ $to be $\,0\,$ or $\,1\,$ since $\,0\,$ is not a common divisor of $\,0,8\,$ and $\,1\,$ is not the greatest common divisor.

The $\iff$ gcd definition is universal - it may be employed in any domain or cancellative monoid, with the convention that the gcd is defined only up to a unit factor. This $\iff$ definition is very convenient in proofs since it enables efficient simultaneous proof of both implication directions. $\ $ For example, below is a proof of this particular form for the fundamental GCD distributive law $\rm\ (ab,ac)\ =\ a\ (b,c)\ $ slightly generalized (your problem is simply $\rm\ c=0\ $ in the special case $\rm\ (a,\ \ ac)\ =\,\ a\ (1,c)\ =\ a\, $).

Theorem $\rm\quad (a,b)\ =\ (ac,bc)/c\quad$ if $\rm\ (ac,bc)\ $ exists.

Proof $\rm\quad d\mid a,b\ \iff\ dc\mid ac,bc\ \iff\ dc\mid (ac,bc)\ \iff\ d|(ac,bc)/c$

See here for further discussion of this property and its relationship with Euclid's Lemma.

Recall also how this universal approach simplifies the proof of the basic GCD * LCM law:

Theorem $\rm\;\; \ (a,b) = ab/[a,b] \;\;$ if $\;\rm\ [a,b] \;$ exists.

Proof $\rm\quad d|\,a,b \;\iff\; a,b\,|\,ab/d \;\iff\; [a,b]\,|\,ab/d \;\iff\; d\,|\,ab/[a,b] \quad\;\;$

For much further discussion see my many posts on GCDs.

$\endgroup$
13
$\begingroup$

Another way to look at it is by the divisibility lattice, where gcd is the greatest lower bound. So 5 is the greatest lower bound of 10 and 15 in the lattice.

The counter-intuitive thing about this lattice is that the 'bottom' (the absolute lowest element) is 1 (1 divides everything), but the highest element, the one above everybody, is 0 (everybody divides 0).

So $\gcd(0, x)$ is the same as ${\rm glb}(0, x)$ and should be $x$, because $x$ is the lower bound of the two: they are not 'apart' and 0 is '$>'$ $x$ (that is the counter-intuitive part).

$\endgroup$
7
$\begingroup$

In fact, the top answer can be generalized slightly: if $a \mid b$, then $\gcd(a,b)=a$ (and this holds in any algebraic structure where divisibility makes sense, e.g. a commutative, cancellative monoid).

To see why, well, it's clear that $a$ is a common divisor of $a$ and $b$, and if $\alpha$ is any common divisor of $a$ and $b$, then, of course, $\alpha \mid a$. Thus, $a=\gcd(a,b)$.

$\endgroup$
  • 1
    $\begingroup$ Indeed, even more generally, it is a special case of the distributive law - see my answer. As for commutative monoids, one usually requires them to be cancellative in order to obtain a rich theory. $\endgroup$ – Bill Dubuque Mar 18 '11 at 18:26
1
$\begingroup$

It might be partly a matter of convention. However, I believe that stating that $\gcd(8,0) = 8$ is safer. In fact, $\frac{0}{8} = 0$, with no remainder. The proof of the division, indeed is that "Dividend = divider $\times$ quotient plus remainder". In our case, 0 (dividend) = 8 (divisor) x 0 (quotient). No remainder. Now, why should 8 be the GCD? Because, while the same method of proof can be used for all numbers, proving that $0$ has infinite divisors, the greatest common divisor cannot be greater than $8$, and for the reason given above, is $8$.

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