Discrete Mathematics

-------------------------------------------------------------COUNTING

249

and hence k::; log

2

(ab)

==

log

2

a+

log

2

b.

Thus,

we

have proved the following.

Theorem The number

of

steps

of

the Euclidean algorithm, applied to two positive integers a and

b,

is at the

most log,

a+

lo~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 really a substantial improvement. For example, the number

of

iterations in

computing the gcd

of

two 300-digit integers is less than 2 log2 10

300

==

600 log

2

10 < 2000. Quite a bit less than

our

first estimate

of

10

100

• Note that log

2