gcd package:semirings

Greatest common divisor. Must satisfy
\x y -> isJust (x `divide` gcd x y) && isJust (y `divide` gcd x y)
\x y z -> isJust (gcd (x * z) (y * z) `divide` z)
Greatest common divisor. Must satisfy
\x y -> isJust (x `divide` gcd x y) && isJust (y `divide` gcd x y)
\x y z -> isJust (gcd (x * z) (y * z) `divide` z)
Execute the extended Euclidean algorithm. For elements a and b, compute their greatest common divisor g and the coefficient s satisfying as + bt = g for some t.
GcdDomain represents a GCD domain. This is a domain, where GCD can be defined, but which does not necessarily allow a well-behaved division with remainder (as in Euclidean domains). For example, there is no way to define rem over polynomials with integer coefficients such that remainder is always "smaller" than divisor. However, gcd is still definable, just not by means of Euclidean algorithm. All methods of GcdDomain have default implementations in terms of Euclidean. So most of the time it is enough to write:
instance GcdDomain Foo
instance Euclidean Foo where
quotRem = ...
degree  = ...