Calculating the GCD: dividing again and again
-----------------------------------------
The Euclidean division theorem provides an algorithm (specifically, Euclid's algorithm) for computing the greatest common divisor, or GCD, of two numbers. For elementary cases, the value of the GCD is obvious at a glance! For instance, the GCD of 21 and 15 is 3. But what about the GCD of 1,597 and 987? Euclid's algorithm lets us compute the GCD of two nonzero natural numbers a and b by successive divisions: we divide a by b; then b by the remainder obtained; then the first remainder by the second remainder; the second by the third… and the last nonzero remainder is the GCD. Thus, the GCD of 1,597 and 987 is 1; these two integers are coprime.
As soon as you have an algorithm, its efficiency becomes a matter of interest. How can it be "measured"? What is the "computation time"? This is the subject of a note — dear to computer scientists today — published in 1844 by Gabriel Lamé (1795–1870). Let's look at what, in the Comptes rendus hebdomadaires de l'Académie des sciences, this newly appointed academician wrote: "In treatises on arithmetic, it is simply stated that the number of divisions to be performed, in finding the greatest common divisor of two integers, cannot exceed half of the smaller one. This limit, which can be exceeded when the numbers are small, becomes excessively loose once they have several digits." He then establishes: "The number of divisions to be performed, to find the greatest common divisor of two integers A and B < A, is always less than five times the number of digits of B [the divisor]."
He ends with an example that highlights the power of his theorem: "Let us take, for example, the two numbers 1,597 and 987. Finding their greatest common divisor will require fourteen divisions. The limit given by the present theorem is fifteen. The limit adopted in treatises on arithmetic would be four hundred and ninety-three."
