gcd 0 0 = 0

Lars Henrik Mathiesen thorinn@diku.dk
18 Dec 2001 16:11:08 -0000


> From: Marc van Dongen <dongen@cs.ucc.ie>
> Date: Tue, 18 Dec 2001 09:32:49 +0000
> 
> Alan Bawden (Alan@LCS.MIT.EDU) wrote:
> : Indeed, that's a nice way of putting it.  How about if the report just
> : says:
> : 
> :    In order to make the non-negative integers into a lattice under `gcd'
> :    and `lcm', we define `gcd 0 0 = 0'.

> It would surely make things a lot less accessible to people
> (including me) who do not have any (or limited) knowledge about
> lattices. Why not make it more accessible and use the following rule
> (ore something similar)?

> The greates common divison (gcd) of two integers a and b is the unique
> non-negative integer g which has each of the following two properties:
>  1) g divides both a and b; and
>  2) if g' also divides both a and b then g' also divides g,
> Here an integer a divides an integer b if there is an integer c
> such that b = c*a.

This is exactly what you get if you plug the relation 'divides' on the
non-negative integers into the definition of meet in a lattice. So
this formulation is no more or less complex to use than the lattice
one --- and people who do know about lattices will probably realize
this pretty fast.

It all depends on who you want to convince that gcd 0 0 should be 0,
the mathematicians (by elegance) or the programmers (by concreteness).
But since it seems that Simon is just going to put 'it is so' in the
report, the point is moot.

Lars Mathiesen (U of Copenhagen CS Dep) <thorinn@diku.dk> (Humour NOT marked)