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