2.2 欧几里得算法

由于公度可能有多个，为此需要引入最大公度（greatest common measure）的概念。如果线段 V 是线段 A 和线段 B 的公度，并且比其他公度都大，则称 V 是 A 和 B 的最大公度。已知两条线段，怎样才能求得最大公度呢？这就引出了历史上著名的递归算法——欧几里得算法（又称辗转相除法）。它用古希腊伟大的数学家欧几里得的名字命名 。在欧几里得的名著《几何原本》第十卷命题三中 ^{[ 11 ]} ，详细阐述了这一算法 。

2.2.1 欧几里得和《几何原本》

欧几里得（Euclid）是古希腊数学家（见图2.7），以其所著的《几何原本》闻名于世。对于他的生平，现在知道的很少。柏拉图学派晚期的导师普罗克洛斯（Proclus）在《几何学发展概要》中记述了这样的趣事：当时的埃及国王，亚历山大的托勒密一世有一次问欧几里得，学习几何学有没有什么捷径可走。欧几里得回答道：“在几何里，没有专为国王铺设的大道。 ”，学习没有捷径成为千古传颂的箴言。斯托比亚斯（Stobaeus）记述另一则故事说，一个学生刚开始学习第一个命题，就问欧几里得学习几何后将得到什么。欧几里得说：“给他三个钱币，因为他想在学习中获取实利。”由此可知欧几里得主张学习必须循序渐进、刻苦钻研，不赞成投机取巧的作风，也反对狭隘的实用观点 ^{[ 11 ]} 。

欧几里得的《几何原本》是一部划时代的著作。其伟大的历史意义在于它是用公理建立起演绎体系的最早典范。过去所积累下来的数学知识是零碎的、片段的，可以比作木石砖瓦。只有借助于逻辑方法，把这些知识组织起来，加以分类比较，解释彼此间的内在联系，整理在一个严密的系统之中，才能建成巍峨的大厦。《几何原本》完成了这一艰巨的任务，它对整个数学的发展产生了深远的影响。

两千多年来，这部著作在几何教学中一直占据统治地位，在20世纪初依然用作数学课的基本教材。现今许多国家仍将其作为中学的必修科目（现在中学的几何课本是按照法国数学家勒让德《几何原本》改写本思路编写的），并作为训练逻辑推理的最有力教育手段 ^{[ 8 ]} 。

2.2.2 欧几里得算法概述

命题2.1 （《几何原本》，卷十，命题三）：已知两个可公度的量，求它们的最大公度量。

欧几里得给出的方法，只需要使用递归和减法。因此本质上可以用尺规作图的方式求出最大公度。这一算法可以形式化如下 ^[3] ：

设两条线段 a 、 b 可公度，如果它们相等，则最大公度就是其中的任一条线段，此时算法返回 a 作为结果。如果线段 a 比 b 长，就用圆规不断从 a 中截去 b （通过递归），然后求截短的线段 a ′和 b 的最大公度；如果线段 b 比 a 长，就反过来不断从 b 中截去 a ，然后求 a 和截短的线段 b ′的最大公度。图2.8描述了这一算法作用于两条线段的计算步骤。我们也可将这一算法应用于整数42和30，并与处理线段的过程进行对比，如表2.1所示。

将一个量 b 反复从另一个量 a 中减去，最后得到 a ′的过程恰好是带余数除法的定义。即 a ′= a -└ a / b 」 b 或记为 a ′= a mod b 。因此我们可以用除法和求余运算代替原始欧几里得算法中的反复相减。此外，当一个量是另一个量的整倍数时，例如 b ≤ a 且 b 可以整除 a ，我们立即知道最大公度为 b 。此时求余的结果 a mod b =0，为此可以定义gcm（0，b）=gcm( b ,0)= b 。我们可以先比较 a 和 b 的大小，如果 a ＜ b 就交换两个量。由于我们知道 a mod b 一定小于 b ，所以下次递归时可以直接交换为gcm( b , a mod b )。这样就得到了改进的欧几里得算法：

为什么这个算法可以求出最大公度呢？我们需要分两步来证明它的正确性。第一步我们要证明这一算法可以求出公度。设 b ≤ a ，令整数 q ₀ 为商， r ₀ 为余数，即 a = bq ₀ + r ₀ ，如果 r ₀ 为零，算法就找到了公度，为此我们考虑 r ₀ 不为零的情况。此时可以进一步列出 b = r ₀ q ₁ + r ₁ ，类似地，只要余数不为零，我们可以一直列出这样的式子。

但只要 a 、 b 是可公度的，这些式子不会无限列下去。理由是每次都用圆规截取整数次，即商是整数。同时每次都保证余数小于除数。即 b ＞ r ₀ ＞ r ₁ ＞ r ₂ ＞…＞0，但是余数不可能小于零。由于起始值是有限的，故最终一定在有限步内得到 r _{n -2} = r _{n -1} q _n 。

接下来我们证明第一步最后得到的 r _{n -1} 可以同时度量 a 和 b 。根据度量的定义，显然 r _{n -1} 可以度量 r _{n -2} 。然后考虑倒数第二式 r _{n -3} = r _{n -2} q _{n -1} + r _{n -1} ，由于 r _{n -1} 可以度量 r _{n -2} ，所以 r _{n -1} 也可以度量 r _{n -2} q _{n -1} ，自然它也可以度量 r _{n -2} q _{n -1} + r _{n -1} ，这个度量恰好等于 r _{n -3} 。用同样的方法，我们可以向上逐一证明 r _{n -1} 可以度量每个式子左边，一直到 b 、 a 。这样我们就证明了欧几里得算法，得到的答案 r _{n -1} 是 a 、 b 的公度。若最大公度为 g ，一定有 r _{n -1} ≤ g 。

第二步我们要证明，任何 a 、 b 的公度 c ，一定也可以度量 r _{n -1} 。由于 c 是公度，因此 a 和 b 可以用它来表示，不妨记 a = mc , b = nc ，其中 m , n 都是整数。这样第一式 a = bq ₀ + r ₀ 就可以写成 mc = ncq ₀ + r ₀ ，我们得知 r ₀ =( m-nq ₀ ) c ，因此 c 也可以度量 r ₀ 。类似地，我们可以依次证明 c 可以度量 r ₁ , r ₂ ,…, r _{n -1} 。这样我们就证明了任何公度都可以度量 r _{n -1} ，因此最大公度 g 也可以度量 r _{n -1} ，即 g ≤ r _{n -1} 。

综合第一、二步的结果，即 r _{n -1} ≤ g 且 g ≤ r _{n -1} ，我们得出最大公度 g = r _{n -1} ，也就是说欧几里得算法能够正确地给出最大公度。进一步，我们知道 g 是每一对量的最大公度，即

图2.9给出了欧几里得算法的一个几何解释。

2.2.3 扩展欧几里得算法

所谓扩展欧几里得算法，就是除了求得两个量 a 、 b 的最大公度 g 外，同时找到满足贝祖（见图2.10）等式 ax + by = g 的两个整数 x 和 y 。为什么贝祖等式（Bézout's identity） 一定成立呢？我们下面给出贝祖等式的一种证明。由 a 、 b 可以构造一个集合，包含它们所有正的线性组合：

S ={ ax + by | x , y ∈Z且 ax + by ＞0}

对于线段来说， S 一定不为空，因为它至少包含 a （此时 x =1, y =0）和 b （此时 x =0, y =1）。因为 S 的所有元素都为正，所以它一定存在一个最小的元素，我们将其记为 g = as + bt 。我们接下来要证明 g 就是 a 和 b 的最大公度。为此我们将 a 表示成 g 的商与余数的形式。

其中余数0≤ r ＜ g 。余数要么为0，要么在集合 S 中。这是因为

即 r 可以表示为 a 、 b 的线性组合，因此如果它不为0，则一定在集合 S 中。但这是不可能的，因为我们之前假设 g 是 S 中的最小正元素，而 r 却比 g 更小，这样就会产生矛盾。因此我们得知 r 一定等于0。根据式（2.4）， g 一定可以度量 a 。用同样的方法，可以证明 g 也一定可以度量 b 。因此 g 是它们的公度。接下来我们证明 g 是最大公度。令 c 为 a 和 b 的任意公度，根据定义，存在整数 m , n 使得 a = mc , b = nc 。这样 g 就可以表示为

这说明 c 可以度量 g ，也就是说 c ≤ g 。这就证明了 g 是最大公度。综上我们就证明了贝祖等式，即存在整数使得 ax + by = g ，并且进一步得知最大公度是所有线性组合的正值中最小的。

使用贝祖等式，我们可以推导出扩展欧几里得算法。

这样就得出了每次递归时的关系：

递归的边界条件出现在 b =0的时候，此时gcm( a ，0)=1 a +0 b 。把边界条件和递归关系归纳起来就得到了扩展欧几里得算法。

我们下面给出一个使用扩展欧几里得算法解决的趣题 ^{[ 14 ]} 。有两个水瓶，一个的容量是9升，另一个的容量是4升。问如何才能从河中打出6升水？

这道题目有很多变化形式，瓶子的容积和取水的容量可以是其他数值。有一个故事说解决这道题目的主人公是少年时代的法国数学家泊松（Simèon Denis Poisson）。

使用两个瓶子，共有6种操作。记大瓶子为 A ，容积为 a ；小瓶子为 B ，容积为 b ：

● 将大瓶子 A 装满水；

● 将小瓶子 B 装满水；

● 将大瓶子 A 中的水倒空；

● 将小瓶子 B 中的水倒空；

● 将大瓶子 A 中的水倒入小瓶子 B ；

● 将小瓶子 B 中的水倒入大瓶子 A 。

其中最后两种操作中，任意一个瓶子满或者另一个瓶子空时就停止。表2.2给出了一系列倒水动作的例子，这里假设容积 b ＜ a ＜2 b 。

无论进行何种操作，每个瓶子中的水的容量总可以表示为 ax + by 的形式，其中 x 、 y 是整数。也就是说，我们能获得的水的体积总是 a 与 b 的线性组合。根据贝祖等式的证明，我们知道线性组合的最小正值恰好是 a 和 b 的最大公度 g 。因此给定两个瓶子的容量，我们立即能够判断是否可以得到体积为 c 的水——只要 c 能够被 g 度量 ^[4] 。这里我们假设 c 不超过两个瓶子中较大瓶子的容积。

例如，使用容量为4升和6升的瓶子，我们永远无法得到5升水。这是因为4与6的最大公约数是2，但5不能被2整除（换个思路想这个问题：用两个容积为偶数升的瓶子，永远无法从河里打到奇数升的水）。如果 a 和 b 是互素的整数，即gcd( a , b )=1，则可以得到任意自然数 c 升的水。

虽然通过检查 g 是否能度量 c 可以判断是否有解，但是我们并不知道具体的倒水步骤。如果我们可以找到整数 x 和 y ，使得 ax + by = c ，就可以得到一组操作来解决此题。具体思路是这样的：若 x ＞0, y ＜0，我们需要倒满瓶子 A 共 x 次，倒空瓶子 B 共 y 次；反之若 x ＜0, y ＞0，则需要倒空瓶子 A 共 x 次，倒满瓶子 B 共 y 次。

例如，若大瓶容积 a =5升，小瓶容积 b =3升，要取得 c =4升水，因为4=3×3-5，即 x =-1、 y =3，我们可以设计如表2.3所示的一系列操作。

在这一系列操作中，倒满 B 共3次，倒空 A 共1次。因此剩下的问题是如何寻找整数 x 和 y ，使得 ax + by = c 。根据扩展欧几里得算法，我们可以找到满足贝祖等式的一组解 ax ₀ + by ₀ = g 。因为 c 是最大公度 g 的 m 倍，我们只要把 x ₀ 和 y ₀ 相应加大 m 倍即可得到一组特解：

根据这组特解，我们可以找到满足不定方程 ^[5] 的所有整数解：

这里 k 为整数。这样我们就找到了倒水问题的所有解。进一步，我们可以找到一个特定的 k ，使得| x |+| y |的值最小，从而得到最快的倒水步骤 ^[6] 。下面是解决这一趣题的Haskell例子程序。

求得两个瓶子倒空和倒满的次数 x , y 后，就可以生成一系列倒水的步骤，本章附录提供了完整的例子程序。

2.2.4 欧几里得算法的意义

在“万物皆数”的哲学思想下，虽然欧几里得算法最初是为了寻找两个整数的最大公约数而产生的，但是经过欧几里得之手，算法却应用到了抽象的几何量上。从整数的最大公约数，到可公度量的最大公度，我们看到了几何量和数的分离 。几何不仅没有建立在整数之上，反而独立发展，解决了整数之外的问题。以至于后来古希腊数学形成了这样的传统：任何关于数的结论，都需要给出几何的证明。这一传统直到16世纪仍然影响着人们。意大利数学家卡尔丹（Gerolamo Cardano） 在关于解三次、四次方程的著作《大术》（Ars Magna，1545年出版）中，仍然使用类似立方体填补法的几何论证 ^{[ 12 ]} 。

欧几里得算法是最著名的一个递归算法。德国数学家、解析数论创始人狄利克雷（Dirichlet）在他的著作《数论讲义》中评价道：“整个数论的结构都建立在同一个基础之上，这个基础就是最大公约数算法。”现代密码学的RSA加密算法 直接使用了扩展欧几里得算法。我们在上一节通过一道趣题展示了如何使用扩展欧几里得算法给出二元线性不定方程 ax + by = c 的整数解。具体来说，就是先求出最大公度 g ，并判断 g 是否整除 c ，若不能，则无整数解。否则，将满足贝祖等式的 x ₀ , y ₀ ，扩大 c / g 倍得到一组特解 x ₁ , y ₁ ，然后得到一般二元线性不定的通解 x = x ₁ -kb / g 和 y = y ₁ + ka / g 。

欧几里得算法是一把锋利的宝剑，但是它强大的递归原理被反过来指向了“万物皆数”的基石——万物可公度。一切事物和现象都可以归结为整数与整数的比，从而引发了毕达哥拉斯学派哲学思想的危机。约公元前470年，毕达哥拉斯学派的学生希帕索思（见图2.11）试图寻找正方形的对角线和边的公度。经过仔细思考，他发现不管度量单位取得多么小，这两条线段都无法公度。还有的说法是希帕索思从毕达哥拉斯学派的神秘五角星标志上得到了启发。毕达哥拉斯学派成员用五角星作为学派的徽章和联络标志。有一则故事说，学派的一个成员流落异乡，贫病交迫，无力酬谢房主的款待，临终前要房主在门上画一个五角星。若干年后，有同派的人看到这个标志，询问事情的经过，厚报房主而去 ^{[ 8 ]} 。美国迪士尼在1959年的动画片《唐老鸭漫游数学奇境》中，描绘了唐老鸭遇到了毕达哥拉斯和他的朋友们，在了解音乐、艺术与数的关系后，唐老鸭的手掌上也画上了神秘的五角星。如图2.12a所示，传说希帕索思发现线段 AC 和 AG 也是无法公度的。

19世纪的苏格兰数学家乔治·克里斯托重建了希帕索思的证明。使用反证法，假设存在一条单位线段 c 能够公度正方形的边和对角线。根据度量的定义，可以令边长为 nc 、对角线长为 mc ，其中 m 、 n 都是正整数。如图2.12b所示，我们以点 A 为圆心，以边长为半径做圆弧交对角线 AC 于点 E 。然后从 E 出发作垂直于对角线的直线，并交边 BC 于点 F 。

根据圆的定义，线段 AE 的长度等于正方形的边长，所以线段 EC 的长度等于( m-n ) c 。因为 EF 垂直于 AC ，而角∠ ECF 是45°，故三角形 ECF 是等腰直角三角形。由于等腰三角形两腰相等，故而有| EC |=| EF |。接下来我们注意两个直角三角形△ AEF 和△ ABF ，由于| AE |等于| AB |，同时 AF 是公共边，因此两个直角三角形全等。这样就得到| EF |=| FB |。综合下来，我们有| EC |=| EF |=| FB |。这样线段 FB 的长度也等于( m-n ) c ，所以线段 CF 的长度等于 CB 的长度减去 FB 的长度，等于 nc -( m-n ) c =（2 n-m ） c 。得到的结论如下所示：

由于 m 、 n 都是正整数，显然 c 也可以公度小正方形的对角线 CF 和边 CE 。仿照上面的方法，我们可以继续作出更小的正方形，并且重复作出无穷无尽的更小的正方形。而 c 总可以公度每一个小正方形的边和对角线。由于 m 、 n 是有限的正整数，这一过程不可能无限做下去，这样就产生了矛盾。于是我们一开始的假设不成立，即正方形的边和对角线不可公度。

这样毕达哥拉斯万物皆数的理论就出现了一个漏洞：存在线段的长度无法用整数比进行度量。据说希帕索思因为这个发现，而遭到谋杀，毕达哥拉斯学派担心这个秘密被泄露出去，而把希帕索思沉入大海。然而历史的车轮不会倒退，古希腊的哲学家和数学家们正视了这个问题，经过欧多克索斯、亚里士多德和欧几里得等人的工作，终于严格定义了不可公度和无理量，并通过几何将它们纳入了古希腊的数学体系。

命题2.2 （《几何原本》，卷十，命题二）：如果从两个不等量的大量中连续减去小量，直到余量小于小量，再从小量中连续减去余量直到小于余量，这样一直做下去，当所余的量总不能量尽它前面的量时，则称两个量不可公度。

这里出现了一个有趣的现象，不可公度是用欧几里得算法能否停止来定义的。由于欧几里得算法是递归的，也就是说递归能否终止成了判断条件。这再次将我们的注意力引入递归的本质上。递归究竟是什么？它怎样用形式化的方法表示？

练习2.1

1.我们给出的欧几里得算法是递归的，请消除递归，只使用循环实现欧几里得算法和扩展欧几里得算法。

2.大多数编程环境中的取模运算，要求除数、被除数都是整数。但是线段的长度不一定是整数，请实现一个针对线段的取模运算。它的效率如何？

3.我们在证明欧几里得算法正确性的过程中说：“每次都保证余数小于除数，即 b ＞ r ₀ ＞ r ₁ ＞ r ₂ ＞…＞0，但是余数不可能小于零。由于起始值是有限的，故最终算法一定终止。”为什么不会出现 r _n 无限接近于零但不等于零的情况？算法一定会终止么？ a 和 b 是可公度的这一前提保证了什么？

4.对于二元线性不定方程 ax + by = c ，若 x ₁ , y ₁ 和 x ₂ , y ₂ 为两对整数解。试证明| x ₁ -x ₂ |的最小值为 b /gcm( a , b )，且| y ₁ -y ₂ |的最小值为 a /gcm( a , b )。

5.边长为1的正五边形，对角线的长度是多少？试证明图2.12的五角星中的线段 AC 和 AG 是不可公度的。使用实数表示，它们的比值是什么？ X58JC4KCJFokUlhu3D4hcVEtoHOikkyc4rUqJwPxvkpAYJ/Ez4ABDCmcB87a7fD2