MIT6-042J-FALL-2010 第四章 数论(Number Theory)_gcd(a, b) = gcd(a, c) = 1.

部分翻译

4  数论(Number Theory)

在这一章中, 我们默认讨论的变量范围是整数, Z.

4.1 整除性 Divisibility

整除关系 

a整除b当且仅当 对于某些k有ak=b (a divides b iff ak D b for some k:)

a整除b简写为a|b.  如果a|b, 我们也可以说b是a的一个倍数.  整除定义的一个推论就是任何数都整除0.

毕达哥拉斯(Pythagoreans)说过, 如果一个数等于它所有的正因子的和, 它就是一个完美数.    6=1+2+3  28=1+2+4+7+14

4.1.1 整除性相关的事实 ( Facts about Divisibility)

引理 (Lemma )  4.1.1

1. 如果 a | b, 那么对于所有的c有a | bc
2. 如果a | b 并且 b | c,那么a | c.
3. 如果 a | b 并且 a | c, 那么对于所有的s和t有 a | sb + tc
4. 对于所有的 c ≠ 0, a | b 当且仅当 ca | cb.

证明: 略

4.1.2 When Divisibility Goes Bad

定理4.1.2 除法定理 (Division Theorem)

假设 n和d是整数, d > 0,那么存在一对唯一的整数 q 和 r, 使得 n= q *d + r ( 0 ≤ r < d )

q 叫做n除以d 的商, r 叫做余数.  用qcnt(n, d)表示商, rem(n, d)表示余数.     qcnt(2716, 10) = 271        rem(2716, 10) = 6

4.1.3 虎胆龙威 Die Hard

经典问题: 用3升和5升的杯子量出4升的水.

引理 4.1.3 假设我们有容量为a和b的容器, 来回地倒, 留在容量中水的量是a和b的线性组合.

证明: 略

4.2  最大公约数 The Greatest Common Divisor

a和b的最大公约数 用gcd(a, b) 表示, 例如 gcd(18, 24) = 6

4.2.1 线性组合与最大公约数  Linear Combinations and the GCD

定理4.2.1 a和b的最大公约数等于它们的线性组合的最小正值.

证明: 略

推论4.2.2 一个整数是a和b的线性组合当且仅当它是a,b最大公约数的倍数.

4.2.2 最大公约数的属性 Properties of the Greatest Common Divisor

引理4.2.4. 对于最大公约数有如下论述:

1. a和b的每个公约数都整除最大公约数.
2. 对于所有的k有gcd(ka, kb) = k * gcd(a,b)
3. 如果gcd(a,b) =1, gcd(a,c) = 1, 那么gcd(a, bc) = 1
4. 如果 a|bc并且 gcd(a,b) = 1 那么a|c
5. gcd(a,b) = gcd(b, rem(a,b))

证明这些引理的一个窍门: 根据定理4.2.1把最大公约数转换为线性组合, 讨论线性组合的性质, 然后再根据定理4.2.1转换回最大公约数. 

4.2.3 欧几里德算法 Euclid’s Algorithm

引理4.2.4的第5条对于快速计算两个数的最大公约数很有用.

比如说, 计算 1147和 899的最大公约数

  gcd(1147, 899)
= gcd(899, rem(1147,899))
= gcd(248, rem(899,248))
= gcd(155, rem(248,155))
= gcd(93, rem(155,93))
= gcd(62, rem(93,62))
= gcd(31, rem(62,31))
= gcd(31, 0)
31
这个计算过程就叫欧几里德算法, 是希腊人在3000年前发现的.

4.2.4 One Solution for All Water Jug Problems

秘诀就是两个瓶子来回倒就行了~~~~

4.2.5 粉碎机 The Pulverizer

The Pulverizer用来求出能得到最大公约数的线性方程的两个参数

现在The Pulverizer通常被叫做扩展的欧几里德GCD算法

对于 259, 70
gcd(259, 70)
= gcd(70, 49)      rem(259, 70) = 259 - 3*70  = 49
= gcd(49, 21)      rem(70, 49)   = 70 - 1*49     = 21
= gcd(21, 7)        rem(49, 21)   = 49 - 2 * 21   = 7
= gcd(7, 0)          rem(21, 7)      = 21 - 3 * 7     = 0
= 7

7 = 49 - 2*21 = (259 - 3 * 70) - 2 * 21 = (259 - 3 * 70) - 2 * (70 - 49) = (259 - 3 * 70) - 2 * (70 - (259 - 3 * 70)) = 3 * 259 - 11 * 70

4.3  算术的基本定理 The Fundamental Theorem of Arithmetic

定理4.3.1 (算术的基本定理).  每个正整数都可以写成唯一的一组质数的乘积.   n = p1 * p2 * ..pj    (p1≤ p2≤...≤pj )

空集合的积被定义为1, 也就是说空集合的积等于1( 空集合的和等于0), 否则n=1时, 定理4.3.1就不成立了.

引理4.3.2 如果p是质数, 并且p|ab, 那么 p|a 或者 p|b.    证明:...

引理4.3.3 设p是一个质数, 如果p|a1a2...an, 那么p整除某个ai

4.4 阿兰 图灵 Alan Turing

信息的加密与解密

4.4.1 图灵的代码(1.0版本) Turing’s Code (Version 1.0)

第一步, 把信息转化成可以计算的数字. 这一步不是为了加密, 所以简单地替换就可以了.假设(a=01, b=02, c=03...), 把消息转换成一个大的数字. 那么 "victory"可以这样转换:

        "v      i    c    t    o    r    y"

->     22 09 03 20 15 18 25

图灵的代码要求消息是一个质数, 所以需要调整数字, 在后面加上适当的数字把消息转换成质数, 在这个例子中,后面加上13, 使它成为一个质数2209032015182513.

加密过程是这样的, 假设m是原来的消息, m'是加密后的消息, k是密钥.

准备工作:  发送者与接收者事先约定一个密钥k, k是一个大质数.

加密:   发送者计算m',   m' = m * k

解密:   接收者解密得到m,  m'/k = m*k/k = m

两个问题:

1. 如何判断一个数是不是质数?

在1970年代早期, 人们已经掌握一种方法, 显然有很小的机率会出错, 但可以忍受了. 

2. 图灵的代码安全吗

要解密, 需要对m'进行因式分解, 这个在当时还是很困难的.

4.4.2 破解图灵的代码  Breaking Turing’s Code

让我们来看看当发送了第二个消息时会发生什么,  m1' = m1 * k

如果敌人拦截了m' 和m1', 我们知道要求两个数的最大公约数是很简单的, 敌人可以通过m' 和m1' 轻松得到密钥k.   很难相信像图灵这么牛X的数学家会忽略这么大一个BUG. 一个可能的解释就是他脑子里的系统稍有不同, 是建立在模运算之上的.

4.5 模运算 Modular Arithmetic