[Haskell-cafe] gcd
Hans Aberg
haberg at math.su.se
Sun May 3 17:11:14 EDT 2009
On 2 May 2009, at 04:05, Steve wrote:
> Why is gcd 0 0 undefined?
In math, one may define gcd(x, y) as a generator of the ideal
generated by x and y in the ring of integers Z. The gcd(x, y) then
always exists as the ring Z is a PID (principal ideal domain), i.e.,
all ideals can be generated by a single element, which can be proven
using Euclid's algorithm, also useful for computing the gcd in Z.
Anyway, the ideal generated by 0 and 0 is the zero ideal 0, which also
is generated by the single generator 0. So gcd(0, 0) = 0 by this
definition.
In Z, one may take the gcd >= 0, but that may not work in every PID.
If k is a field, then the polynomial ring k[x] is a PID, but not the
ring k[x_1, ..., x_n]. So that leads to Buchberger's Groebner Basis
Algorithm.
Hans
More information about the Haskell-Cafe
mailing list