The exponent has fixed type Integer in order to avoid an arbitrarily limitted range of exponents, but to reduce the need for the compiler to guess the type (default type). In practice the exponent is most oftenly fixed, and is most oftenly 2. Fixed exponents can be optimized away and thus the expensive computation of Integers doesn't matter. The previous solution used a ToInteger constrained type and the exponent was converted to Integer before computation. So the current solution is not less efficient.

A variant of ^ with more flexibility is provided by ringPower.

reduceRepeated is an auxiliary function that, for an associative operation op, computes the same value as

reduceRepeated op a0 a n = foldr op a0 (genericReplicate n a)

but applies op O(log n) times and works for large n.

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.

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