gcd package:numeric-prelude

The Greatest Common Divisor is defined by:
gcd x y == gcd y x
divides z x && divides z y ==> divides z (gcd x y)   (specification)
divides (gcd x y) x
It is only a monoid for non-negative numbers.
idt <*> GCD (-2) = GCD 2
Thus, use this Monoid only for non-negative numbers!
Compute the greatest common divisor and solve a respective Diophantine equation.
(g,(a,b)) = extendedGCD x y ==>
g==a*x+b*y   &&  g == gcd x y
TODO: This method is not appropriate for the PID class, because there are rings like the one of the multivariate polynomials, where for all x and y greatest common divisors of x and y exist, but they cannot be represented as a linear combination of x and y. TODO: The definition of extendedGCD does not return the canonical associate.
Compute the greatest common divisor for multiple numbers by repeated application of the two-operand-gcd.