# gcd definition

S.D.Mechveliani mechvel@math.botik.ru
Sun, 16 Dec 2001 15:35:57 +0300

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

*
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

```