gcd 0 0 = 0
Tue, 18 Dec 2001 13:12:14 -0500
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
> ... 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":
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.