gcd 0 0 = 0

[Michael Ackerman]

The general meaning of `having a prime factorization' is that every
non-zero element is uniquely a product of a unit and a product of
primes. The algebraic structures where unique factorizations live are
`unique factorization domains' (UFDs) of which a central class is formed
by the ring of polynomials over a field. Here the non-zero elements of
the field are the units; no one has ever suggested calling them primes!

In a general UFD one can only speak of _a_ gcd of two elements x and y,
meaning an element d such that one has (x, y) = (d), an equality of
ideals. In some special cases, there is a natural choice for d (e.g., in
the integers, the non-negative d; in the ring of polynomials over a
field, the monic d (having leading coeff. 1)). In some UFDs there is no
canonical choice (e.g. in the Gaussian integers, a + ib for a, b integers).

gcd(0, 0) = 0.

Cheers,
Michael Ackerman

Dylan Thurston wrote:
> 
> 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
> 
> _______________________________________________
> Haskell mailing list
> Haskell@haskell.org
> http://www.haskell.org/mailman/listinfo/haskell