gcd 0 0 = 0

[S.D.Mechveliani]

People write on  gcd 0 0 :

Alan Bawden <Alan@LCS.MIT.EDU>

> 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.


Frank Seaton Taylor <fstaylo@alpha.ncsc.mil> writes

T> Let me chime in in favor of gcd(0,0) = 0 rather than undefined.
T>
T> On Tuesday, December 11, 2001, at 01:07 , Alan Bawden wrote:
T>
T> > Also, it is nice to be able to know that gcd(x, 0) = x for -all- x.
T>
T> Alan is in good company:
T>
T> 1. Steele in "Common Lisp: The Language" says the same thing.
T>
T> 2. Knuth in "The Art of Computer Programming" defines gcd(0,0)=0.
T> classic algebra


All right. Let us try to investigate this.
In such cases one should consult mathematics, not programming.
So, let us ignore "Common Lisp ...".
And Knuth is all right, I think.

Further, the definintion 

>   gcd(x, y) to be the smallest 
> z >= 0 such that {m*x + n*y | m, n in Z} = {n*z | n in Z}

is not natural. In particular, how does it generalize to  gcd X Y
for polynomials in X, Y with rational coefficients?
It is 1. And how would one obtain     1 = f*X + g*Y  ?

According to classic algebra (Kummer, I guess),

  gcd x y   in (such and such) domain R 
            is the least by inclusion principal ideal  (g) 
            that includes the ideal  (x, y).

  Here  (a1..an) = set of all combinations  y1*a1 + .. + yn*an,
                   yi from R.

According to this definition,  gcd (X) (Y) = (1)
in polynomials, all right, 
and                            gcd n m  :: Integer  is  (0)

Because (0) is the least by inclusion principal ideal containing (0).

And this also contradicts the part "greatest integer that divides ..."
in recent Haskell specification.
Probably, the best specification would be
  
  gcd n m :: Integer = if  n == 0 && m == 0  then  0
                       else
                         greatest integer that divides both n and m
 
-----------------
Serge Mechveliani
mechvel@botik.ru