数论初步-南京大学计算机科学与技术系

《数论初步-南京大学计算机科学与技术系》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数论初步离散数学南京大学计算机科学与技术系提要整数的性质整数的基本运算质数Euler函数与Euler定理什么是数论？现代数论的早期铺垫整数集整数的代数性质整除余数余数同余质数质数质数质数的性质质数定理最大公约数最大公约数的性质求最大公约数的Euclid算法中国剩余定理（孙子定理）中国剩余定理欧拉函数欧拉定理归纳与递归离散数学南京大学计算机科学与技术系提要数学归纳法强数学归纳法运用良序公理来证明递归定义结构归纳法什么是数学归纳法数学归纳法的逻辑基础数学归纳法证明目标nP(n)//n的论域为正整数集合证明框架基础步骤：P(1)为真归纳步骤：对任意正整数k,P

2、(k)P(k+1).//即，证明k(P(k)P(k+1))因此，对任意正整数n,P(n)成立.//即：nP(n)数学归纳法（有效性）良序公理正整数集合的非空子集都有一个最小元素数学归纳法的有效性（归谬法）假设nP(n)不成立，则n(P(n))成立.+令S={n

3、P(n)}，S是非空子集.根据良序公理，S有最小元素，记为m,m1(m-1)S,即P(m-1)成立.根据归纳步骤，P(m)成立，即mS，矛盾.因此，nP(n)成立.数学归纳法（举例）Hk=1+1/2+…+1/k（k为正整数）n证明：H21+n/2（n为正整数）基础步骤：P

4、(1)为真，H=1+1/22归纳步骤：对任意正整数k,P(k)P(k+1).Hk+1=Hk+1/(2k+1)+…+1/2k+122(1+k/2)+2k(1/2k+1)=1+(1+k)/2因此，对任意正整数n,P(n)成立.数学归纳法（举例）猜测前n个奇数的求和公式，并证明之。1=11+3=41+3+5=91+3+5+7=16…21+3+…+(2n-1)=n（n为正整数）运用数学归纳法证明（练习）数学归纳法证明时常见错误数学归纳法证明时常见错误强数学归纳法证明目标nP(n)//n的论域为正整数集合证明框架基础步骤：P(1)为真归纳步骤：对任意正整数k

5、,P(1),…,P(k)P(k+1).//即，证明k(P(1)…P(k)P(k+1))因此，对任意正整数n,P(n)成立.//即：nP(n)强数学归纳法（一般形式）设P(n)是与整数n有关的陈述，a和b是两个给定的整数，且ab.如果能够证明下列陈述P(a),P(a+1),…,P(b).对任意kb,P(a)…P(k)P(k+1)则下列陈述成立对任意na,P(n).{nZ

6、na}是良序的强数学归纳法（举例）任意整数n(n2)可分解为（若干个）素数的乘积n=2.考察k+1.用4分和5分就可以组成12分及以上的每种邮资.P(12),P(1

7、3),P(14),P(15).对任意k15,P(12)…P(k)P(k+1)数学归纳法（举例）n对每个正整数n4，n!2基础步骤：P(4)为真，2416归纳步骤：对任意正整数k4,P(k)P(k+1).(k+1)!=(k+1)k!(k+1)2k2k+1因此，对任意正整数n4,P(n)成立.运用良序公理来证明（举例）设a是整数,d是正整数,则存在唯一的整数q和r满足0r

8、0a-dq，qZ}，S非空.非负整数集合具有良序性S有最小元，记为r=a-dq.00可证0r

9、在循环赛胜果图中，若存在长度为m（m3）的回路，则必定存在长度为3的回路。备注：aiaj表示ai赢了aj证明设最短回路的长度为k（k3）//良序公理的保证aaa…aa123k1若aa,存在长度为3的回路，矛盾。31若aa,存在长度为(k-1)的回路，矛盾。13递归结构递归结构递归定义（N上的函数）递归地定义自然数集合N上的函数。基础步骤：指定这个函数在0处的值；递归步骤：给出从较小处的值来求出当前的值之规则。举例，阶乘函数F(n)=n！的递归定义F(0)=1F(n)=nF(n-1)forn>0Fibonacci序列Fibonacci序列{

10、fn}定义如下f=0,0f=1,1f=f+f,对任意n2.nn–1n–2其前几个数0,1,1,2,3,5,8,…nn证明：对任意n0，fn1515其中，,.22归纳证明:Fibonacci序列验证：当n=0,1时，陈述正确。对于k+1,fffk1kk1kkk1k1kk1kk1k1k1.注意：2=+1，且n+1=n