102 6. Integers, Divisors, and Primes
6.6.9Describe the Euclidean Algorithm applied to two consecutive Fibonacci
numbers. Use your description to show that the Euclidean Algorithm can take
arbitrarily many steps.
So whatcanwe say about how long the Euclidean Algorithm lasts? The
key to the answer is the following lemma:
Lemma 6.6.1During the execution of the Euclidean Algorithm, the prod-
uct of the two current numbers drops by a factor of at least 2 in each
iteration.
Proof.To see that this is so, consider the step where the pair (a, b)(a<b)
is replaced by the pair (r, a) (recall thatris the remainder ofbwhen divided
bya). Then we haver<aanda+r≤b. Henceb≥a+r> 2 r, and so
ar <^12 abas claimed.
Suppose that we apply the Euclidean Algorithm to two numbersaand
band we makeksteps. It follows by Lemma 6.6.1 that after theksteps,
the product of the two current numbers will be at mostab/ 2 k. Since this
is a positive integer and so at least 1, we get that
ab≥ 2 k,and hence
k≤log 2 (ab) = log 2 a+ log 2 b.Thus we have proved the following.
Theorem 6.6.2The number of steps of the Euclidean Algorithm applied
to two positive integersaandbis at mostlog 2 a+ log 2 b.
We have replaced the sum of the numbers by the sum of the logarithms of
the numbers in the bound on the number of steps, which is a really substan-
tial improvement. For example, the number of iterations in computing the
g.c.d. of two 300-digit integers is less than 2 log 210300 = 600 log 210 <2000.
Quite a bit less than 2· 10300 , which was our first naive estimate! Note that
log 2 ais less than the number of bits ofa(when written in base 2), so we
can say that the Euclidean Algorithm does not take more iterations than
the number of bits needed to write down the numbers in base 2.
The theorem above gives only an upper bound on the number of steps
the Euclidean Algorithm takes; we can be much luckier. For example, when
we apply the Euclidean Algorithm to two consecutive integers, it takes only
one step. But sometimes, one cannot do much better. If you did exercise
6.6.9, you saw that when applied to two consecutive Fibonacci numbersFk
andFk+1, the Euclidean Algorithm takesk−1 steps. On the other hand,