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