2 Greatest common divisor

This algorithm is perhaps the most common operation that is used in computing with large integers after the basic operations. It is also the first an algorithm was written (since this algorithm was written before the base 10 arithmetic operations that we saw earlier). We will study three algorithms and their extensions. The fundamental question is to find the greatest common divisor or highest common factor d of a pair a, b of integers. One also knows that there is a formula ax + by = d and in some applications it is necessary to determine x and y as well. A more general problem that this is to find a free basis for a subgroup of a free group (or ``lattice''). We will see how to solve that problem in later sections.