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