gcd 0 0

Alan Bawden Alan@LCS.MIT.EDU
Tue, 11 Dec 2001 13:07:51 -0500 (EST)


   From: George Russell <ger@tzi.de>
   Date: Tue, 11 Dec 2001 18:18:31 +0100
   ...
   Yes.  The Report definition says
      gcd              :: (Integral a) => a -> a -> a
      gcd 0 0          =  error "Prelude.gcd: gcd 0 0 is undefined"
      gcd x y          =  gcd' (abs x) (abs y)
			  where gcd' x 0  =  x
				gcd' x y  =  gcd' y (x `rem` y)

   On reflection, this is quite right.  a divides b <=> there is an
   integer n with na = b.  Thus any integer divides 0, and so the
   "greatest common divisor" would have to be the greatest integer,
   which is nonsense. 

   Of course if you adopt Stephan Kahrs definition of "greatest", taken
   with respect to the partial order a<=b <=> a divides b, then gcd 0 0 =
   0, because 0 is indeed the greatest integer in this ordering.
   Mathematically this makes sense, but it's not necessarily what people
   expect.

If you take the point-of-view that gcd is actually an operation on
ideals, then gcd(0, 0) is 0.  I.e. define gcd(x, y) to be the smallest 
z >= 0 such that {m*x + n*y | m, n in Z} = {n*z | n in Z}.  This is
probably the most natural and general definition of gcd, and is, in fact,
what many mathematicians would expect.

Also, it is nice to be able to know that gcd(x, 0) = x for -all- x.