gcd definition

[S.D.Mechveliani]

Simon Peyton-Jones  <simonpj@microsoft.com>  writes

> [..]
> If someone could write a sentence or two to explain why gcd 0 0 = 0,
> (ideally, brief ones I can put in the report by way of explanation),
> I think that might help those of us who have not followed the details
> of the discussion. 


Here it is.

  gcd n m :: Integer = if  n == 0 && m == 0  then  0
                       else
                         greatest integer that divides both n and m

It is set so according to classic definition
(by Pythago, Euclid ...)  

  GCD x y =  such g that divides both x and y and is a multiple 
             of any g' that divides both x and y.

In particular,   GCD 0 0 :: Integer = 0   and can be nothing else.
Because
        0 divides 0 and divides nothing else,  
        everything divides 0  (z*0 = 0).





Other comments  -------------------------------------------------

*
People say, D.Knuth writes  gcd 0 0 = 0  in his book.
And he is a known mathematically reliable person.

*
Example.   gcd 12 18 :: Integer =  6  or  -6,   
                          
because 6 divides 12 and 18, and any other such number divides 6.

*
The Haskell report says "greatest integer" for domain = Integer,  
and thus, chooses the sign `+' for the result.
This choice is not a mistake and helps to write shorter programs.

*
All the above agrees with the modern generic theory of ideals 
(started in |XX by Kummer, Gauss, Lagrange)
for any commutative domain  R  having the properties of
                (a /= 0, b /= 0 ==> a*b /= 0),
                existence of unique factorization to primes.
According to it
  gcd x y = 
  least by inclusion ideal of kind (g) that includes the ideal 
  (x, y),
  where Ideal     (a,b..c) =def= {x*a + y*b +..+ z*c | x,y..z <- R}
  - a subset in R.
  `includes` (as set) is a partial order on ideals, and it is true 
  that
             (1)  a divides b  <==>  (a) includes (b),
             (2)  (a) includes (a).

Specializing this definition to Integer, we obtain the source 
formula.
 
-----------------
Serge Mechveliani
mechvel@botik.ru