** Next:** 2.1 Euclid's algorithm
** Up:** Some Lectures on Number
** Previous:** 1.6 GMP and other

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.

**Subsections**

Kapil Hari Paranjape
2002-10-20