gcd 0 0 = 0

Alan Bawden Alan@LCS.MIT.EDU
Thu, 13 Dec 2001 22:55:31 -0500 (EST)


   From: "S.D.Mechveliani" <mechvel@math.botik.ru>
   Date: Thu, 13 Dec 2001 12:53:32 +0300

   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?

Well, that -is- the way gcd is defined in the commutative algebra textbook
I used in graduate school -- I just specialized the definition for the case
of the ring of integers, and so I didn't mention that Z was a principle
ideal domain.  Polynomials in two variables aren't a PID, so yes, you'd
have to restore some things I left out.  When I said my definition was
"general" I suppose I should have anticipated someone would generalize in a
way I hadn't intended...  (Actually, that definition doesn't even
generalize exactly to the Gaussian Integers, where "z >= 0" would have to
be replaced by some specification of a region of the complex plane.)

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

Fortunately, we all seem to agree on what the actual definition should be.

I did make a mistake in my previous message.  I said that it was nice that
gcd(0, x) = x for all x.  I should have said: gcd(0, x) = abs(x).