数论应用选讲课件.ppt

数 论 应 用 选 讲 李学武 2006年1月 绵阳 数论是研究数的性质的学科，是一门古老而充满现代魅力的数学学科。数论基本上可分为初等数论、解析数论、代数数论等几个较大的分支。 在古代，我国对数论的研究曾有过有辉煌的成就, 如孙子定理（国外文献一般称为中国剩余定理）、商高定理(勾股数)、圆周率的计算等等。在现代，我国一些著名的数学家，如华罗庚、王元、陈景润、潘承洞、丁夏畦等都在数论领域做出了一些举世公认的重要成果。 过去，人们把数论归类为纯粹数学，但现在在许多领域，数论的原理和定理都得到了广泛的应用。例如计算机的计算模型、硬件体系结构和软件的设计与实现、代数编码、计算机通信安全与密码学等方面, 都有着数论知识的广泛应用。近年来发展起来的一门新兴学科“算法数论”就是用计算机算法来研究和深化数论的理论。一个高层次的计算机专业人员，应该掌握数论的一些基础知识。 1．求解二元一次不定方程 2．求解三元一次不定方程 3．佩尔方程 4．Fibonacci数列 1．求解二元一次不定方程 我们的任务是解二元一次不定方程 ax+by=c ①其中a,b,c都是整数，所求的解(x,y)也是整数。 方程①如果有解，则解不是唯一确定的，所以我们称①为不定方程。 二元一次不定方程是一类重要的方程，应用很广。关于方程①的可解性，有下面的两个重要的结论： （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) 也都是方程①的解。 下面我们讨论具体求解的方法。 为了避免计算中对负数和0的讨论，我们假定a0，b0，并且a=b。 假定方程①有解，即系数满足：gcd(a,b)|c，这时，c’=c/gcd(a,b)一定是个整数。我们先讨论下面的方程： ax+by=f ②其中f=gcd(a,b)，右端项恰好是左边两系数的最大公因子。显然，如果(x0,y0)是方程②的一组解，则(c’x0,c’y0)也是方程①的一组解，即a(c’x0)+b(c’y0)=(c’f)=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*(-15)+73*22=1,于是，③的一组解为（-15，22）。 下面归纳一般的算法：将(1)-(5)写成一般的形式：si=ti*qi+ri， qi=si/ti， ri=si%ti， si+1=ti，ti+1=ri 认真分析上面的规律，可以归纳出具体的求解方法。我们先用下面的表格列出相应的关系： 关键算法是x[k]，y[k]的递推计算公式：x[0]=0，x[1]=1； x[i+1]=x[i]*q[i]+x[i-1]， 当i1时。y[0]=1，y[1]=q[0]； y[i+1]=y[i]*q[i]+y[i-1]，当i1时。当 t[k]≠0 且 r[k]=s[k]%t[k]=0 时，k就是最后一轮计算，这时，x[k]=15，y[k]=22 就是所要的结果，但要加上适当的符号后，才能得到原方程的解(x,y)： x=(-1)k-1x[k]，y=(-1)ky[k]。 程序：#include stdio.hvoid result_one(int a,int b,int c,int *x2,int *y2)/* 函数1：计算不定方程的一组解 */ {int q[200],x[200],y[200