Proposal: Make gcd total

Daniel Fischer daniel.is.fischer at googlemail.com
Sun May 29 17:25:09 CEST 2011


On Sunday 29 May 2011 02:15:41, wren ng thornton wrote:
> The only con I can envision is that, in the general case, the uniqueness
> of gcd is guaranteed by various properties; whereas every number is a
> divisor of 0.

But that makes 0 the largest/greatest element (in the divisibility 
preorder), whence gcd 0 0 = 0 follows.

Actually, that's the only case where the algebraic definition of a gcd 
results in a unique representative, in all other cases¹, a rule to pick one 
representative of an equivalence class is needed to make it a (single-
valued) function (of type a -> a -> a).

In the case of (rational) integers, Z, picking the non-negative element of 
an equivalence class {x, -x} is a fairly natural choice (but for other 
purposes, a different choice may be more suitable, e.g. it can be more 
convenient to pick the representative congruent to 1 (mod 4) for odd primes 
instead of the positive one).

> So, given the uniqueness criterion one could make an
> argument. However, the common mathematical practice takes gcd 0 0 == 0,
> and I'm unaware of a compelling reason not to do so.

Indeed all but two options are completely ridiculous. The only defensible 
options are to leave gcd 0 0 undefined or to have gcd 0 0 = 0.

The former has the merit of allowing the term 'greatest' to refer to the 
normal archimedian order of Z and making the term explicable in concepts 
familiar to everyone, but that has the serious drawback of restricting the 
rings in which gcds exist to ordered rings with only two units (1 and -1).


[¹] except if the ring has only one unit



More information about the Libraries mailing list