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.