大学课件:数论基础及应用.ppt
《大学课件:数论基础及应用.ppt》由会员分享,可在线阅读,更多相关《大学课件:数论基础及应用.ppt(19页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、1,数论基础及应用,2,数论是研究数的性质的学科是一门古老而充满现代魅力的数学学科。数论基本上可分为初等数论、解析数论、代数数论等几个较大的分支。,3,在古代,我国对数论的研究曾有过辉煌的成就, 如孙子定理(国外文献一般称为中国剩余定理)、商高定理(勾股数)、圆周率的计算等等。在现代,我国一些著名的数学家,如华罗庚、王元、陈景润、潘承洞、丁夏畦等都在数论领域做出了一些举世公认的重要成果。,4,过去,人们把数论归类为纯粹数学,但现在在许多领域,数论的原理和定理都得到了广泛的应用。例如计算机的计算模型、硬件体系结构和软件的设计与实现、代数编码、计算机通信安全与密码学等方面, 都有着数论知识的广泛应
2、用。近年来发展起来的一门新兴学科“算法数论”就是用计算机算法来研究和深化数论的理论。一个高层次的计算机专业人员,应该掌握数论的一些基础知识。,5,1欧几里德转辗相除法,利用gcd(a,b)=gcd(b,a mod b)求a,b的最大公约数: Function gcd(a,b:longint):longint;beginif b=0 then gcd:=a Else gcd:=gcd(b,a mod b);end; 思考:如何把上述算法写成迭代形式?,6,2扩展的欧几里德算法,如果gcd(a,b)=d,一定存在整数x和y满足gcd(a,b)=ax+by。,算法的理论根据: 由欧几里德转辗相除法
3、gcd(a,b)=gcd(b,a mod b), 设整数x、y满足gcd(b,a mod b)=bx+(a mod b)y 则ax+by=bx+(a mod b)y =bx+(a-(a div b)*b)y =ay+b(x-(a div b)y) 于是 x=y y=x-(a div b)y,7,求d及满足gcd(a,b)=ax+by的整数对(x,y)的算法,function exgcd(a,b:longint;var ,y:longint):longint;vart:longint;beginif b=0 thenbegin exgcd:=a; x:=1; y:=0;end,8,求d及满足gc
4、d(a,b)=ax+by的整数对(x,y)的算法(续),elsebeginexgcd:=exgcd(b,a mod b,x,y);t:=x;x:=y;y:=t-(a div b)*y;end; end;,思考: 1)如何把上述算法写成迭代形式? 2)满足gcd(a,b)=ax+by的整数对(x,y)是否是唯一的?,9,应用1:求解二元一次不定方程ax+by=c整数解,解二元一次不定方程 ax+by=c 其中a,b,c都是整数,所求的解(x,y)也是整数,10,关于方程的可解性,有下面的两个重要的结论:,(1)设gcd(a,b)表示整数a,b的最大公约数。方程有解的充分必要条件是gcd(a,b)
5、|c。(记号“x|y”表示x能整除y,即存在整数k,使y=kx)。 (2)如果(x0,y0)是方程的一组解,则对任何整数t,(x0+bt,y0-at)也都是方程的解。 下面我们讨论具体求解的方法。 为了避免计算中对负数和0的讨论,我们假定a0,b0,并且a=b。 假定方程有解,即系数满足:gcd(a,b)|c,这时,c=c/gcd(a,b)一定是个整数。我们先讨论下面的方程: ax+by= gcd(a,b) 根据上述扩展的欧几里德算法,一定存在整数x0和y0满足ax+by =gcd(a,b)。 显然,如果(x0,y0)是方程的一组解,则(cx0,cy0)也是方程的一组解,即 a(cx0)+b(
6、cy0)=(cf)=c。,11,求二元一次不定方程ax+by=c一组整数解(x0,y0)的算法,procedure equation(a,b,c:longint;var x0,y0:longint);var d,x,y:longint;begind:=exgcd(a,b,x,y);参见扩展的欧几里德算法if c mod d0 thenbegin writeln(no answer); halt;end elsebegin x0:=x*(c div d); y0:=y*(c div d);end;end;,说明: (1)如果a,b中有一个小于0,例如a0,可以令x=-x,解方程 ax+by=c。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 大学 课件 数论 基础 应用
限制150内