最大公约数

《哈代数论》第1.1节首先对整除性作出定义:

称一个整数 a 能被另一个整数 b (b≠0) 整除(divisible),假设存在第3个整数 c 使得 a = bc。用记号 b|a 来表示 a 被 b 整除,或 b 是 a 的一个因子(divisor)。

第2.9节给出了最大公约数的定义:

定义两个不全为零的整数 a 和 b 的最大公约数(highest common divisor)d:如果 d 是能同时整除 a 和 b 的最大正整数。记为 d = (a,b)。于是有 (0,a) = |a|。可以用同样的方法定义任意一组正整数 a,b,c,...,k 的最大公约数 (a,b,c,...,k)。

highest common divisor 或 highest common factor 是英国数学界对最大公约数的称呼(本书作者G.H.哈代和E.M.赖特都是英国数学家),而更为普遍的说法是 gcd(greatest common divisor)。

第2.9节接着证明了下面这个重要的定理(注意:这里我们所说的数都是指整数,因为这是数论):

定理25 对任意给定的不全为零的整数 a 和 b,令 d = (a,b),方程 ax + by = n 有整数解 x, y,当且仅当 d|n。特别地,ax + by = d 可解。

证明 对任意给定的不全为零的整数 a 和 b,考虑所有形如 ax + by 的整数组成的集合 S,假设 c 是 S 中的最小正数(S 中含有正数是显而易见的),如果 n 是 S 中任何一个正数,那么对所有的 z,n - zc ∈ S。如果 r 是 n 被 c 除得到的余数,且 n = zc + r,则有 r ∈ S 且 0 ≤ r < c。既然 c 是 S 中的最小正数,故有 r = 0 以及 n = zc。同样的推理对 S 中的负数也成立。所以,S 是某个正数 c 的倍数 zc 组成的集合。由于 c 整除 S 中的每一个数,所以它必整除 a 和 b,于是 c ≤ d。另一方面,由 d|a, d|b 可得 d|(ax + by),所以 d 整除 S 中的每一个数,特别有 d|c。由此推得 c = d,于是 S 就是 d 的倍数组成的集合。这就证明了定理。


欧几里得算法

第12.3节介绍了欧几里得算法(在中国称为辗转相除法,可追溯至东汉出现的《九章算术》):

假设 a ≥ b > 0。用 b 除 a 得到 a = q1b + r1,其中 0 ≤ r1 < b。如果 r1 ≠ 0,则可以重复这个程序得到 b = q2r1 + r2,其中 0 ≤ r2 < r1。如果 r2 ≠ 0,则有 r1 = q3r2 + r3,其中 0 ≤ r3 < r2。如此一直下去。非负整数 b, r1, r2, … 构成一个递减序列,故必然有某个 n 使得 rn+1 = 0。这个程序中的最后两步是
        rn-2 = qnrn-1 + rn (0 < rn < rn-1),
        rn-1 = qn+1rn
关于 r1, r2, … 的这一组方程称为欧几里得算法

正如同下面的定理所指出的那样,欧几里得算法包含了求 a 和 b 的最大公约数的常用程序。

定理207 rn = (a,b)。

证明 令 d = (a,b)。那么,通过连续使用这个算法,我们得到
        d|a, d|b → d|r1 → d|r2 → … → d|rn
所以 d ≤ rn。再次倒推回去,即得
        rn|rn-1 → rn|rn-2 → rn|rn-3 → … → rn|b → rn|a。
于是 rn 同时整除 a 和 b。由于 d 是 a 和 b 的公约数中的最大者,故得到 rn ≤ d,从而有 rn = d。


参考资料

  1. 哈代数论(第6版),[英]G.H.哈代 E.M.赖特 著,张明尧 张凡 译,人民邮电出版社,2010年10月第1版
  2. An Introduction to the Theory of Numbers, 6th Edition, G. H. Hardy, Edward M. Wright, Oxford University Press, September 15, 2008
  3. 维基百科:辗转相除法

评论

推荐 2
抓个小错。定理207中,“于是 d 同时整除 a 和 b”,应为r_n而非d。手头没中文版,看了下英文版没错。
谢谢,已改。你说得有道理,应该是 r_n 。书放在单位了,明天上班核对一下是我打错了还是书上错了。 –  空军 2013-04-16 18:00
是书上错了,我看得也不够认真。已提交勘误建议:第184页第17行“于是 d 同时整除 a 和 b”应改为“于是 r_n 同时整除 a 和 b”,这条勘误是隋春宁提供的。 –  空军 2013-04-17 08:42

推荐 1
图片太大了
仅仅是引用 http://www.ituring.com.cn/book/119 的已有图片(在我的浏览器中会自动缩小以适应页面),没有重新上传。 –  空军 2013-04-16 16:03
有3MiB –  lt 2013-04-16 16:47
嗯,虚心接受。我把它下载下来,改变大小,制作了一幅只有 56K 的图片上传了。:) –  空军 2013-04-16 18:08

推荐 1
这些定义、定理和算法在最近的编程也快乐第三期正好用得上。
具体数学同样的译者不知道为什么译成最大公因子 –  lt 2013-04-16 16:00
确实是同样两位译者。 –  空军 2013-04-16 16:05

我要评论

需要登录后才能发言
登录未成功,请修改提交。