[Haskell-cafe] Re: gcd

Nathan Bloomfield nbloomf at gmail.com
Sun May 3 02:35:04 EDT 2009

Having gcd(0,0) = 0 doesn't mean that 0 is not divisible by any other
natural number. On the contrary, any natural trivially divides 0 since n*0 =
0. Perhaps the disagreement is over what is meant by "greatest". The
"greatest" in gcd is not w.r.t. the canonical ordering on the naturals;
rather w.r.t. the partial order given by the divides relation. Similarly for
the "least" in lcm.

Suppose gcd(0,0) = a. Then a|0, and if b|0 then b|a. (That's what it means
to be the gcd.) So what is a? Since every natural number divides zero, a
must be divisible by every natural number. The only natural number with this
property is 0, which can be proved using the essential uniqueness of prime
factorizations and infinitude of primes.

So having gcd(0,0) = 0 isn't just useful, it's the correct thing to do.

I hope that didn't use too many long words. :)

-Nathan Bloomfield
Grad Assistant, University of Arkansas, Fayetteville

On Sat, May 2, 2009 at 5:17 PM, Achim Schneider <barsoap at web.de> wrote:

> Steve <stevech1097 at yahoo.com.au> wrote:
> > "It is useful to define gcd(0, 0) = 0 and lcm(0, 0) = 0 because then
> > the natural numbers become a complete distributive lattice with gcd
> > as meet and lcm as join operation. This extension of the definition
> > is also compatible with the generalization for commutative rings
> > given below."
> >
> Ouch. Speak of mathematicians annoying programmers by claiming that 0
> isn't divisible by any of [1..], and further implying that 0 is bigger
> than all of those, not to mention justifying all that with long words.
> Damn them buggers.
> --
> (c) this sig last receiving data processing entity. Inspect headers
> for copyright history. All rights reserved. Copying, hiring, renting,
> performance and/or quoting of this signature prohibited.
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20090503/2e48e222/attachment.htm

More information about the Haskell-Cafe mailing list