# gcd 0 0 = 0

Lars Henrik Mathiesen thorinn@diku.dk
17 Dec 2001 14:50:21 -0000

```> From: Marc van Dongen <dongen@cs.ucc.ie>
> Date: Sun, 16 Dec 2001 13:35:59 +0000
>
> Marc van Dongen (dongen@cs.ucc.ie) wrote:
>
> :   An integer \$a\$ divides integer \$b\$ if there exists an integer
> :   \$c\$ such that \$a c= b\$.
>
> To make clear why \$0\$ (and not any other non-zero integer) is the
> gcd of \$0\$ and \$0\$ I should have added that for the integer case
> \$g\$ is called a greatest common divisor (gcd) of \$a\$ and \$b\$ if it
> satifies each of the following two properties:
>
>  1) \$g\$ divides both \$a\$ and \$b\$;
>  2) if \$g'\$ is a common divisor of \$a\$ and \$b\$ then \$g'\$ divides \$g\$.

In case it isn't clear already, these definitions make a lattice on
the positive integers, with divides ~ leq, gcd ~ meet and lcm ~ join,
using the report's definitions of gcd and lcm.

(Choosing the positive result for gcd/lcm is equivalent to noting that
divides is a partial preorder on the non-zero integers, and that the
quotient identifies x and -x).

The only thing that is lacking to make it a lattice on the
non-negative integers, is that  gcd 0 0 = 0 . All other cases
involving zero (i.e.,  gcd 0 x = x  for non-zero x, and  lcm 0 x = 0
for all x) are consistent with 0 being the maximal element in the
lattice, i.e., that all integers divide zero.

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

```