Euclid's algorithm for computing the greatest common divisor of 2 numbers is considered to be the oldest proper algorithm known. It has been well and truly studied and analyzed. Euclid's algorithm can be amplified naturally in various ways. The GCD problem for more than two numbers is interesting in its own right. We will consider how to compute multiple GCDs well in the worst case.

Also, we can do a constructive computation, the so-called extended GCD, which expresses the GCD as a linear combination of the input numbers. Extended GCD computation plays a basic role in various fundamental algorithms. It dates back to at least Euler. We will look at how hard it is to compute extended GCDs well.