# Proposal: Make gcd total

Sebastian Fischer fischer at nii.ac.jp
Thu May 19 10:51:50 CEST 2011

+1

On Tue, May 10, 2011 at 12:49 AM, Daniel Fischer <

> I would like to propose the elimination of the special error case
>
> gcd 0 0 = error "Prelude.gcd: gcd 0 0 is undefined"
>
> to replace it with
>
> gcd 0 0 = 0
>
> (which would be an automatic consequence of removing the above line).
>
> Rationale:
>
> 1. It makes gcd a total function.
> 2. It makes gcd associative.
> 3. It makes folding gcd over a list safe.
> 4. It conforms to common mathematical practice:
>
> In a commutative ring, a greatest common divisor of two elements a, b is
> a common divisor g of a and b such that every common divisor d of a and b
> also divides g (if R is a commutative ring, a \in R, d \in R is a divisor
> of a iff there exists c \in R with a = d*c [leaving out noncommutative
> rings for simplicity]).
> Since every ring element divides 0, the above definition entails
> gcd 0 0 = 0.
>
> Further, in a principal ideal ring, the greatest common divisors of two
> elements a and b are the generators of the ideal (a,b), again that
> characterisation of greatest common divisors says gcd 0 0 = 0:
> (0,0) = {0} = (0).
>
> Pros: see above.
>
> Cons: ?
> I'm not aware of any, the change shouldn't break existing code, since that
> would have to check for the special case anyway.
>
> Daniel
>
> _______________________________________________