gcd 0 0 = 0

[Dylan Thurston]

On Tue, Dec 18, 2001 at 06:00:30PM +0100, Kent Karlsson wrote:
> Why?  If EVERY natural number is to have a  prime factorisation, then BOTH
> 0 AND 1 have to be promoted to prime numbers;

1 has a perfectly fine prime factorization.  It is the product of 0 primes,
the null product.  (A null product is defined, for very good reasons, to
be 1, just like a null sum is defined to be 0.)

I could see defences of calling 0 a prime, although it is not standard
mathematical practice.  The ideal generated by 0 is a prime ideal,
for one thing.  0 would still not have a unique prime factorization,
however.  (But Haskell should not unilaterally decide to violate standard
mathematical terminology!)

> ... But
> there is a fundamental reason to say that 0 can never be a divisor (i.e. 0|0
> is false; x|y is true iff x is a *non-zero* factor of y; the 'non-zero' part
> is often left implicit (e.g. one is only talking about strictly positive
> integers), which is part of the reason why we are having this discussion).

What fundamental reason do you have in mind?  Why do you use this definition
of divisibility?  (I'm curious; other mathematicians give the same
definition, and I can't see why.)

This thread made me curious, so I did a little library research.  I was
surprised to discover that mathematicians discover on this, the domain
of definition of "gcd a b":

Domain		  References
------		  ----------
a /= 0, b /= 0	  Lang, "Algebra, 3rd Edition"
		  Hasse, "Number Theory"

a, b not both 0	  Koblitz, "A Course on Number Theory and Cryptography"

all a, b allowed  MacLane and Birkhoff, "Algebra, 2nd Edition"
		  Koch, "Number Theory"

At least the books by Lang and MacLane-Birkhoff are standard references.
Note that the definitions all agree when they are defined (with gcd 0 0 = 0).

As I said, I was surprised; to me, the definiton with all a and b is the
more natural one.  I still recommend using the full domain (especially since
exceptions are awkward to deal with in Haskell), but I'm not as certain.

Best,
	Dylan Thurston