gcd 0 0 = 0
Michael Ackerman
ack@nethere.com
Tue, 18 Dec 2001 15:54:13 -0800
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