资源描述：
《数论基础及应用.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、数论基础及应用1数论是研究数的性质的学科是一门古老而充满现代魅力的数学学科。数论基本上可分为初等数论、解析数论、代数数论等几个较大的分支。2在古代，我国对数论的研究曾有过辉煌的成就,如孙子定理（国外文献一般称为中国剩余定理）、商高定理(勾股数)、圆周率的计算等等。在现代，我国一些著名的数学家，如华罗庚、王元、陈景润、潘承洞、丁夏畦等都在数论领域做出了一些举世公认的重要成果。3过去，人们把数论归类为纯粹数学，但现在在许多领域，数论的原理和定理都得到了广泛的应用。例如计算机的计算模型、硬件体系结构和软件的设计与实现、代数编码、计算机通信安全与密码学等方面,都有
2、着数论知识的广泛应用。近年来发展起来的一门新兴学科“算法数论”就是用计算机算法来研究和深化数论的理论。一个高层次的计算机专业人员，应该掌握数论的一些基础知识。41．欧几里德转辗相除法利用gcd(a,b)=gcd(b,amodb)求a，b的最大公约数：Functiongcd(a,b:longint):longint; begin ifb=0thengcd:=aElsegcd:=gcd(b,amodb); end;思考：如何把上述算法写成迭代形式？52．扩展的欧几里德算法如果gcd(a,b)=d，一定存在整数x和y满足gcd(a,b)=ax+by。算法的理论
3、根据：由欧几里德转辗相除法gcd(a,b)=gcd(b,amodb)，设整数x’、y’满足gcd(b,amodb)=bx’+(amodb)y’则ax+by=bx’+(amodb)y’=bx’+(a-(adivb)*b)y’=ay’+b(x’-(adivb)y’)于是x=y’y=x’-(adivb)y’6求d及满足gcd(a,b)=ax+by的整数对（x，y）的算法functionexgcd(a,b:longint;var,y:longint):longint; var t:longint; begin ifb=0then begin exgcd:=a
4、; x:=1; y:=0; end7求d及满足gcd(a,b)=ax+by的整数对（x，y）的算法（续）else begin exgcd:=exgcd(b,amodb,x,y); t:=x; x:=y; y:=t-(adivb)*y; end;end;思考：1）如何把上述算法写成迭代形式？2）满足gcd(a,b)=ax+by的整数对（x，y）是否是唯一的？8应用1：求解二元一次不定方程ax+by=c整数解解二元一次不定方程ax+by=c①其中a,b,c都是整数，所求的解(x,y)也是整数9关于方程①的可解性，有下面的两个重要的结论：（1）
5、设gcd(a,b)表示整数a,b的最大公约数。方程①有解的充分必要条件是gcd(a,b)
6、c。（记号“x
7、y”表示x能整除y，即存在整数k，使y=kx）。（2）如果(x0,y0)是方程①的一组解，则对任何整数t,(x0+bt,y0-at)也都是方程①的解。下面我们讨论具体求解的方法。为了避免计算中对负数和0的讨论，我们假定a>0，b>0，并且a>=b。假定方程①有解，即系数满足：gcd(a,b)
8、c，这时，c’=c/gcd(a,b)一定是个整数。我们先讨论下面的方程：ax+by=gcd(a,b)②根据上述扩展的欧几里德算法，一定存在整数x0和y0满足ax+
9、by=gcd(a,b)。显然，如果(x0,y0)是方程②的一组解，则(c’x0,c’y0)也是方程①的一组解，即a(c’x0)+b(c’y0)=(c’f)=c。10求二元一次不定方程ax+by=c一组整数解（x0,y0）的算法procedureequation(a,b,c:longint;varx0,y0:longint); vard,x,y:longint; begin d:=exgcd(a,b,x,y);{参见扩展的欧几里德算法}ifcmodd<>0then begin writeln('noanswer'); halt; endelse
10、begin x0:=x*(cdivd); y0:=y*(cdivd); end; end;说明：（1）如果a,b中有一个小于0，例如a<0，可以令x’=-x，解方程ax’+by=c。求解后，再令x=-x’就可以了。（2）利用前面讲过的性质：“如果(x0,y0)是方程①的一组解，则对任何整数t,(x0+bt,y0-at)也都是方程①的解”。可以通过任何整数t得到方程①的其余解。11递推法求二元一次不定方程ax+by=c一组整数解（x0,y0）我们先讨论下面的方程：ax+by=f②其中f=gcd(a,b)例如方程107x+73y=1③其中a=107,b=
11、73,f=1我们用类似于求最大公约数的辗转相除的方法求这个解。利用
