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 > [EMAIL PROTECTED] > http://www.haskell.org/mailman/listinfo/haskell _______________________________________________ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
