数论应用选讲.ppt

1、数 论 应 用 选 讲,李学武 2006年1月 绵阳,数论是研究数的性质的学科，是一门古老而充满现代魅力的数学学科。数论基本上可分为初等数论、解析数论、代数数论等几个较大的分支。,在古代，我国对数论的研究曾有过有辉煌的成就, 如孙子定理（国外文献一般称为中国剩余定理）、商高定理(勾股数)、圆周率的计算等等。在现代，我国一些著名的数学家，如华罗庚、王元、陈景润、潘承洞、丁夏畦等都在数论领域做出了一些举世公认的重要成果。,过去，人们把数论归类为纯粹数学，但现在在许多领域，数论的原理和定理都得到了广泛的应用。例如计算机的计算模型、硬件体系结构和软件的设计与实现、代数编码、计算机通信安全与密码学等方面

2、, 都有着数论知识的广泛应用。近年来发展起来的一门新兴学科“算法数论”就是用计算机算法来研究和深化数论的理论。一个高层次的计算机专业人员，应该掌握数论的一些基础知识。,1求解二元一次不定方程 2求解三元一次不定方程 3佩尔方程 4Fibonacci数列,1求解二元一次不定方程 我们的任务是解二元一次不定方程 ax+by=c 其中a,b,c都是整数，所求的解(x,y)也是整数。 方程如果有解，则解不是唯一确定的，所以我们称为不定方程。,二元一次不定方程是一类重要的方程，应用很广。关于方程的可解性，有下面的两个重要的结论： （1）设gcd(a,b)表示整数a,b的最大公约数。方程有解的充分必要条件

3、是 gcd(a,b)|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=f 其中f=gcd(a,b)，右端项恰好是左边两系数的最大公因子。显然，如果(x0,y0)是方程的一组解，则(cx0,cy0)也是方程的一组解，即a(cx0)+b(cy0)=(cf

4、)=c。,在方程中，取a=107,b=73,c=1，显然满足gcd(107,73)=1，方程 107x+73y=1 有解。我们用类似于求最大公约数的辗转相除的方法求这个解。利用辗转相除，可以得到： 107=73*1+34, (1) 73=34*2+5, (2) 34=5*6+4, (3) 5=4*1+1, (4) 4=1*4。 (5),为了消去(3)中的”4”，令 (3)*1-(4): 34=5*7-1 (6) 为了消去(2)中的”5”，令 (2)*7-(6): 73*7=34*15+1 (7) 为了消去(1)中的”34”，令(1)*15-(7): 107*15=73*22-1, 即：107*

5、(-15)+73*22=1,于是，的一组解为（-15，22）。,下面归纳一般的算法：将(1)-(5)写成一般的形式：si=ti*qi+ri， qi=si/ti， ri=si%ti， si+1=ti，ti+1=ri,认真分析上面的规律，可以归纳出具体的求解方法。我们先用下面的表格列出相应的关系：,关键算法是xk，yk的递推计算公式：x0=0，x1=1； xi+1=xi*qi+xi-1， 当i1时。y0=1，y1=q0； yi+1=yi*qi+yi-1，当i1时。当 tk0 且 rk=sk%tk=0 时，k就是最后一轮计算，这时，xk=15，yk=22 就是所要的结果，但要加上适当的符号后，才能得

6、到原方程的解(x,y)： x=(-1)k-1xk，y=(-1)kyk。,程序：#include void result_one(int a,int b,int c,int *x2,int *y2)/* 函数1：计算不定方程的一组解 */ int q200,x200,y200; int d1,d2,i,r,t,j,gcd; x0=0;y0=1; d1=a;d2=b; for(i=0;i200;i+) qi=d1/d2; r=d1%d2; d1=d2;d2=r; if(r=0) gcd=d1; break; ,if(i=0) x1=1; y1=q0; else xi+1=qi*xi+xi-1; y

7、i+1=qi*yi+yi-1; for(t=-1,j=1;ji;j+) t=-t; *x2=-t*xi; *y2=t*yi;/* 以上求方程ax+by=gcd(a,b)的一组解 */,if(c%gcd!=0) printf(No solution!n); exit(0); t=c/gcd; *x2=*x2*t; *y2=*y2*t;/* 以上求方程ax+by=c的一组解 */ ,main()/* 函数3：主函数 */ int a,b,c,x2,y2; printf(Input a(0),b(0),c:n); scanf(%d%d%d, ,关于算法，还要说明两点：（1）如果a,b中有一个小于0，

8、例如a0，y0-at0就可以得到全部正整数解。,习题： 现有容量为M，N升的两个罐子（依次记为A,B）没有任何刻度，要求从水池中量出K升水放到另一个容器里。其中M,N,K都是正整数。例如，对于M=7,N=3,K=1，可以这样操作，先用A罐量M升水，再利用B罐从A罐中量两次N升水，A罐中剩余的就是所要的1升水。编程输出操作过程，或输出“不可能”。,2求解三元一次不定方程我们的任务是解二元一次不定方程 ax+by+cz=d 如果a,b,c中有一个数绝对值为1，例如a=1,z则有 x=d-by-cx,在具体计算中，如果不存在a=1,可取绝对值最小的一个系数，例如仍然是a，将方程表为,例：求解方程 6x+20y-15z=23 ,3佩尔方程问题：由键盘输入一个整数N(N109)，求不超过N的最大整数n,使 是一个完全平方数。,分析：由对于一般的佩尔方程： x2-dy2=1, 当d0且d是完全平方数时，解只有（1，0）或 （-1，0）。,下面假定d0且d不是完全平方数，设(x1,y1)是方程的最小解 则全部正整数解可表为：,4Fibonacci数列（1995年NOI）已知整数m,n满足： (n2-nm-m2) 2=1， (1)求m2+n2的最大值，其中m,n106由键盘输入。,分析：如果m=n，只能有m=n=1，因此可假定 mn，不妨设mn。令n=m+uk，由(1)可