1.2.5 Greatest Common Divisors

The greatest common divisor (GCD) of two integers a and b is

defined to be the largest integer that divides both a and b with no

remainder. For example, the GCD of 16 and 28 is 4. In Chapter 2, when we investigate how to implement rational-number arithmetic, we will

need to be able to compute GCDs in order to reduce rational numbers

to lowest terms. (To reduce a rational number to lowest terms, we must divide

both the numerator and the denominator by their GCD. For example,

16/28 reduces to 4/7.) One way to find the GCD of two integers is to

factor them and search for common factors, but there is a famous algorithm that

is much more efficient.

两个整数 a 与 b 的最大公约数（GCD）定义为能同时整除 a 和 b 的最大整数。例如，16 与 28 的最大公约数是 4。在第 2 章讨论如何实现有理数算术时，我们需要能够计算最大公约数，以便将有理数化简为最简形式。（将有理数化简为最简形式，就是将分子和分母同除以它们的最大公约数。例如，16/28 化简为 4/7。）求两个整数的最大公约数，一种方法是对它们做因式分解后寻找公因子，但有一个著名的算法效率更高。

The idea of the algorithm is based on the observation that, if r is the

remainder when a is divided by b, then the common divisors of a and

b are precisely the same as the common divisors of b and r. Thus,

we can use the equation

该算法的思想基于如下观察：若 r 是 a 除以 b 的余数，则 a 与 b 的公约数恰好与 b 和 r 的公约数完全相同。因此，我们可以利用等式

to successively reduce the problem of computing a GCD to the problem

of computing the GCD of smaller and smaller pairs of integers. For

example,

反复将计算最大公约数的问题归约为计算越来越小的一对整数的最大公约数。例如，

reduces GCD(206, 40) to GCD(2, 0), which is 2. It is

possible to show that starting with any two positive integers and performing

repeated reductions will always eventually produce a pair where the second

number is 0. Then the GCD is the other number in the pair. This

method for computing the GCD is known as

将 GCD(206, 40) 逐步归约为 GCD(2, 0)，其结果为 2。可以证明，从任意两个正整数出发，反复执行这种归约，最终必然得到第二个数为 0 的序对，此时另一个数就是所求的最大公约数。这种求最大公约数的方法称为

Euclid’s Algorithm.

It is easy to express Euclid’s Algorithm as a procedure:

欧几里得算法。将欧几里得算法表达为一个过程非常容易：

This generates an iterative process, whose number of steps grows as the

logarithm of the numbers involved.

这将产生一个迭代型计算过程，其步骤数随所涉及数的对数增长。

The fact that the number of steps required by Euclid’s Algorithm has

logarithmic growth bears an interesting relation to the Fibonacci numbers:

欧几里得算法所需步骤数具有对数增长这一事实，与斐波那契数有一个有趣的关联：

Lamé’s Theorem: If Euclid’s Algorithm requires k steps to

compute the GCD of some pair, then the smaller number in the pair

must be greater than or equal to the k

拉梅定理：若欧几里得算法求某对整数的最大公约数需要 k 步，则该序对中较小的数必须大于或等于第 k

th Fibonacci number.

个斐波那契数。

We can use this theorem to get an order-of-growth estimate for Euclid’s

Algorithm. Let n be the smaller of the two inputs to the procedure. If

the process takes k steps, then we must have

n

≥

我们可以用这个定理来估计欧几里得算法的增长的阶。设 n 为该过程两个输入中较小的那个。若计算过程共需 k 步，则必有 n ≥

Fib
(
k
)
Fib(k)

≈

φ
k
φ^k

/

5. Therefore the number of steps k

grows as the logarithm (to the base φ) of n. Hence, the order of

growth is Θ

(

log

⁡

n

).

√5。因此，步骤数 k 以 n 的对数（以 φ 为底）的速度增长，即增长的阶为 Θ(log n)。