[Haskell-cafe] gcd

[Hans Aberg]

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