计算机问题求解 – 论题4-1 - 数论基础 2017年03月20日.

Presentation on theme: "计算机问题求解 – 论题4-1 - 数论基础 2017年03月20日."— Presentation transcript:

1 计算机问题求解 – 论题 数论基础 2017年03月20日

2 问题1: 自然数有定义吗?

3 from What is Mathematics, by Courant and Robbins

4 用集合定义自然数 设a为集合, 称a{a}为a的后继, 记为或a+, 或s(a)。 设A是集合，若A满足下列条件，称A为归纳集：
自然数集合N是所有归纳集的交集。 因此：N = { Ø, {Ø}, {Ø, {Ø}}, {Ø, {Ø}, {Ø, {Ø}}}, … } N的每一个元素称为一个自然数。 Ø记为0，0+记为1，1+记为2，2+记为3，余此类推

5 再具体一点 记号0表示：Ø 记号1表示0+： Ø{Ø}={Ø} 记号2表示1+： {Ø}{{Ø}}={Ø,{Ø}}
记号3表示2+: {Ø,{Ø}}{{Ø,{Ø}}}={Ø,{Ø}, {Ø,{Ø}}} 3∪2=? 3∩2=? 23? 13? 12? 25? 自然数上的小于关系如何表达？ 3 2 Y 以上四种交、并、属于、包含于运算均可以定义小于关系。

6 自然数上的运算 加法（递归定义） 乘法（递归定义） 序关系 m+0=m m+n+=(m+n)+ m*0=0 m*n+=m + m*n
ab iff cN. a+c=b

7 问题2: 关于自然数有“公理”吗？ 皮亚诺公理

8 关于整数的公理 对于加法与乘法封闭； 加法与乘法满足交换律； 加法与乘法满足结合律； 乘法对加法满足分配律；
加法和乘法各自有单位元素（0和1） 方程a+x=0有整数解（称为a的逆元素，并可由此定义“减法”） 如果c0，ac=bc  a=b（消去律） （基于{1,2,3,…}定义“正整数”和“大于”、“小于”）对任意a，a>0, a=0, 和a<0三者必有其一，也仅有其一； 任一正整数的非空集合必含最小元素（良序性）

9 良序性与数学归纳法原理 任何定义在自然数上的命题，均可以用数学归纳法进行证明。 在计算机科学中，更是如此

10 问题3: 你能说说为什么归纳法原 理与良序性质是等价的吗? 归纳法可行蕴含良序：用归纳法证明良序：给定任意自然数的子集S，S均拥有最小元素
奠基：如果1在该子集中，成立；（可以用数学归纳法证明1是自然数中最小的数） 假设：所有包含了一个小于等于n的自然数（命名为k）的子集，均包含最小元素。 归纳：（所有包含了一个小于等于n+1的自然数的子集，也拥有最小元素）任取一个包含了一个小于等于n+1的自然数的子集：如果这个子集中包含了小于等于n的元素，按照归纳假设，这个子集包含最小元素；如果这个子集不包含小于等于n的元素，n+1必定在这个子集中，n+1将成为最小元素。 结论：自然数集是良序的。 良序可以保证归纳法的正确性：假设归纳法是错误的。 假设归纳法是错误的。在自然数集合上，必定存在若干个元素x1,x2,…,xk,使得P(xi)不成立。定义X为这个集合。X是良序的，命x是X集合的最小元素。X至少大于等于2（归纳法中的奠基已经证明了P(1)是成立的），因为x是最小元素，所以x-1不在X中，P(x-1)成立的。根据归纳法，P(1)成立，P(x-1)成立，P(x)也成立。产生矛盾

11 良序可以保证归纳法的正确性： 证明策略：反证法（假设归纳法是错误的） 假设归纳法是错误的：
在自然数集合上，必定存在若干个元素x1,x2, …, xk,使得P(xi)不成立。 定义X为这个集合。X是良序的，命x是X集合的最小元素，P(x)为假。 x至少大于等于2（归纳法中的奠基已经证明了P(1)是成立的），因为x是最小元素，所以x-1不在X中，P(x-1)成立的。根据归纳法，P(1)成立，P(x-1)成立，P(x)也成立。 产生矛盾。 结论：归纳法是正确的。

12 归纳法可行蕴含良序 用归纳法证明良序：给定任意自然数的子集S，S均拥有最小元素 奠基：如果1在该子集中，成立；
假设：所有包含了一个小于等于n的自然数（命名为k）的子集，均包含最小元素。 归纳：（所有包含了一个小于等于n+1的自然数的子集，也拥有最小元素）任取一个包含了一个小于等于n+1的自然数的子集：如果这个子集中包含了小于等于n的元素，按照归纳假设，这个子集包含最小元素；如果这个子集不包含小于等于n的元素，n+1必定在这个子集中，n+1将成为最小元素。 结论：自然数集是良序的。

13 问题4: 数论中用的最多的等式之一 这明明是个“定理”，为什么被称为“算法”？ 找到q和r是非常有意思的: r被限定为“余数” B被称为模
在整数加群中，a和b：存在一个c：a=b+c

14 存在性的证明 这个集合里，到底是哪些元素？ 为什么让k=2a? 模b后的余数及 b的倍数和余数的和 保证大于0 保证适用良序

15 唯一性的证明 在数论相关证明中，整除时时出现！

16 整除及其性质 线性组合 问题5：如果a是b,c的最大公因子，这个结论会给你什么启发？ b和c的公因子可以整除b和c的任意线性组合；

17 现在你知道如何“算”出ab的最大公因子了吗？ “最大公因子”是公因子
构造出“最大公因子” 现在你知道如何“算”出ab的最大公因子了吗？ “最大公因子”是公因子 任给两个互质的整数a,b，总是能够找到他们的某种线性组合ra+sb，构造出1，然后将线性组合乘以m,得到任意的整数m：mra+msb 而且一定是最大公约数

18 Euclid Algorithm – 数学形式
ab的线性组合，小于a,b ab的线性组合，小于r1 ab的线性组合，小于rn-1 +0 ab的线性组合，=0 rn是……r1,r2的公因子，是a,r1的公因子，是b,a的公因子

19 问题5： 你知道为什么用两个互质的整数的线性 组合可以表示任意的整数吗？
任给两个互质的整数a,b，总是能够找到他们的某种线性组合ra+sb，构造出1，然后将线性组合乘以m,得到任意的整数m：mra+msb

20 问题6： 你能看出每个序列中元素间的关系吗？ 1, 3, 5, 7, 9, 11, … 奇数： 2, 4, 6, 8, 10, …. 偶数：
平方数： 立方数： 质数： 合数： 模4余1： 模4余3： 三角数： 完全数： Fibonacci: 1, 3, 5, 7, 9, 11, … 2, 4, 6, 8, 10, …. 1, 4, 9, 16, 25, 36, … 1, 8, 27, 64, 125, … 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, … 4, 6, 8, 9, 10, 12, 14, 15, 16, … 1, 5, 9, 13, 17, 21, 25, … 3, 7, 11, 15, 19, 23, 27, … 1, 3, 6, 10, 15, 21, … 6, 28, 496, … 1, 1, 2, 3, 5, 8, 13, 21, … 问题6： 你能看出每个序列中元素间的关系吗？

21 问题7： 你是否能说出一些关于质 数的“著名”问题？

22 关于质数 我们在课堂上很容易回答的问题： 今天可以给你一个答案，却难以证明的问题： 还没有人能回答的问题： 质数是有限的还是有无穷多个？
不大于一个给定值的质数有多少个？ 还没有人能回答的问题： 是否任何不小于４的偶数均可以表示为两质数之和 “孪生”质数对(p和p+2) 是否有无限多个？ 形如n2+1的质数是否有无限多个？ 素数定理：素数的分布规律的描述

23 质数有无限多个 一些“大”数学家认为这是数学史上最“美”的证明之一！ π

24 利用费马数证明质数有无穷多个 为什么？ 假设质数有限，为m个。取前m+1个费马数。将每个费马数进行质因子分解，所有的质因子都不相同。M+1个费马数至少有m+1个互不相同的质因子。因此矛盾。 证明： 1）任意两个费马数都是互质的。 2）假设质数有限，为m个。取前m+1个费马数。将每个费马数进行质因子分解，所有的质因子都不相同。M+1个费马数至少有m+1个互不相同的质因子。因此矛盾。 为何是互质的呢？ 反证法：如果Fk和Fn有公因子m，Fk=a*m, Fn=b*m. Fn-2=b*m-2= F0*F1*…*Fk*…*F(n-1)=F0*F1*…*F(n-1)*a*m=a’*m b*m-2=a’*m (b-a’)*m=2 m是2的因子，m不能为2，m=1.

25 用抽象代数理论证明质数无限 问题８； 你能解释一下这个证明吗？ 定义P是所有素数的集合，其中p是最大的素数。
找到2^p-1这个数，该数大于p，是合数。对其进行质因子分解。我们要证明，其中的任意一个质因子都大于p。取质因子q： 1），找到q的剩余乘代数系统Zq\{0};比如Z5\{0}为{1,2,3,4}。这是一个群。元素个数是q-1 2），在这个群里，元素2的阶是p，因为2^p模q为1. 3），根据拉格朗日定理，p是q的因子。 所以，q比p大 问题８； 你能解释一下这个证明吗？

26 算术基本定理；质因子分解 存在性：良序性 唯一性：归纳法 如何证明存在性？证明的关键：
唯一性：归纳法证明 奠基：2的质因子分解是唯一的。 假设：对于所有小于n的m，其质因子分解是唯一的。 归纳：假设n可以表达为两种不同的分解方式：n=p1*p2*…*pk=q1*q2*…*ql。显然，p1是素数+能够整除q1*q2*…*ql，p1一定是某个q的因子，p1一定等于某个qi，同理，q1也一定等于某个pj。 此时，p1=q1. 令n‘=q2*…*ql=p2*…*pk=q1*q2。根据归纳假设，形式相同。 结论：唯一。 存在性：采用良序性和反证法 令a是所有不能进行质因子分解的数中最小的合数。A必定能够分解为两个数a1，a2的积。A1，a2均小于a，能够质因子分解。A也就能够质因子分解。 如何证明存在性？证明的关键： 存在性：如果a是不能分解的整数中最小的，它不能是质数，则必可分解为两个数之积，那两个数一定可分解，于是a也可分解。 唯一性：将两个质因子分解式均按升序排列，对应项只能相等。

27 问题９： 如何判断一个数是否为 质数？ 你听说过 Eratosthenes 的“筛子”吗？ x 10 100 1000 10000 106
109 (x) 4 25 168 1229 78498 x/ln(x) 4.34 21.71 144.76 (x)/(x/ln(x) 0.921 1.151 1.161 1.132 1.084 1.054

28 Open Topics： 1，请总结一下，在哪些你所学过的内容中，我们用到了数学归纳法？ 写出欧几里得算法，证明算法的正确性