浅谈一次不定方程的求解问题--大学生毕业论文.doc

【标题】浅谈一次不定方程的求解问题 【作者】吴 艳 【关键词】一次不定方程观察法辗转相除法连分数数法矩阵法 【指导老师】邓 淙 【专业】数学与应用数学 【正文】1.引言11引言“不定方程”是指未知数的个数多于方程个数的方程，这类方程可能有无穷多解。一般的，我们把这类方程的解定义在整数或正整数的范围中。这样一来，方程的解就具有了稳定性。对于不定方程的求解问题属于数论的研究范畴。它具有悠久的历史，古今中外有不少数学家对此进行了探讨。在西方被称之为不定方程鼻祖的丢番都（Diophantus）是系统研究不定方程的第一人，在我国古代“百鸡问题”几乎成了此类方程的代名词。近年来，不定方程的求解问题更是各类竞赛的热点之一，并有向课本渗透的趋势。例如，人民教育出版社出版高中数学第二册（上）中“线性规划”这一小节中找整数解问题，就属于此类问题，而这些题目往往是学生学习的难点。总的来说，不定方程的类型很多，且解法具有多样性。对于一次的方程的解的求法，通常是用观察法、辗转相除法、连分数法、矩阵法、取特殊模法等等。通过一系列实例，说明了解一次不定方程（组）常用的方法，并对文献3提出的观察法作了深入的讨论，进行了推广。此外，适当联系了高中新教材的相关内容，对中学数学教学有一定的参考价值。最后，本文介绍了一次不定方程中著名的Frobenius问题，与大家共赏。至于高次的多元的不定方程，迄今为止，只有少数具体的特例被人搞清楚，还有广阔的未知领域。12引用定理为了方便讲解，本文引用了如下定理：定理1.2.11：二元一次不定方程：（1）(其中a,b,c是整数且都不是0)有整数解的充分必要条件是（a,b）c。定理1.2.2：设（1）式有一整数解x=x0,y=y0，又设（a,b）=d, a=a1d,b=b1 d则（1）的一切解可以表示成：,其中定理1.2.3:设 a,b是任意两个正整数，可得： k=1,2-n，其中:若（a,b）=1,则方程有一组特解：定理1.2.42：若（a,b）=1,且化为连分数 a1,a2,a3,-an，设的前的一近数是，由连分数的性质得：即:两边乘以c，成为：与（1）式比较得其特殊解是：.一次不定方程的常用解法本文用以上定理来探讨一次不定方程的一些主要解法。1观察法：观察法是一种比较简易的方法，但使用此法的前提条件是不定方程的系数比较简单，通过观察就能得到它的一组特殊整数解（x0,y0），再利用定理1.2.2的通解公式求出其它各个整数解。如果系数较为简单时，观察法不失为一种快捷，省事的好办法。例13中国古代数学家张丘建在他编写的张丘建算经里，曾经解过这样的一道题目：“鸡翁一，值钱五，鸡母一，值钱三，鸡雏三，值钱一，百钱买百鸡，问鸡翁鸡母鸡雏各几何？”解：设用x,y,z分别代表，鸡翁，鸡母，鸡雏的数目，就得到下面的方程组：消去z，再化简得：7x+4y=100显然这是个关于x,y二元一次方程，由观察法可知（7，4）=1，1能整除100，所以方程有整数解，又因为，所以x0=0,y0=25为方程的一组特解，由定理2可知方程通为：x=-4t,y=25+7t。由题意得：方程的解的范围在一百以内，所以方程的解为：,。从”百鸡问题”我们可以看出,按x的值来说,两个相邻的特解相差y的系数值,按y的值来说,每个相邻特解相差x的系数值，这对我们理解和记忆通解公式有所帮助。由上面的例题大家可得出利用观察法的关键是找特殊解，因为任何事物的矛盾都是普遍性和特殊性的辨证统一，普遍性存在特殊性中，特殊性里包含着普遍性。找到了特解，我们才能从特殊推到一般。如何才能更快更准确找到特殊解呢？这就需要有一定的技巧，文献3中指出,形如（1）式的不定方程，在以下几种情形，可以通过观察法，简便的求出特殊解。情形1：如果a|c,那么就令y=0。如果b|c,那么就令x=0,例2求3x+5y=9的通解解：因为（3，5）|9，所以此方程有整数解。又因为3|9，所以令 y=0,代入方程得x=3,所以方程的一组特解为：（3，0），方程的通解为: t z例3：求的通解解：因为（5，2）|6，所以此方程有整数解。又因为2|6，所以令x=0，代入方程得,所以方程的一组特解为：（0，-3）由此得方程的通解为： t z情形2:若(a+b)|c，设，则方程（1）有特殊解例4:求4x+7y=11的一个特解解:因为(4,7)=1,1|11,有整数解,4,7都不能整除11.但发现系数之间存在着4+7=11的特点,即(a+b)|c,容易看出:所以方程的通解为: t z例5：求的一组特解。解：因为，所以方程有特解（3，3）例6:求5x-4y=3的通解解:此题(5,4)=1,1|3,有整数解,属于(a-b)|c的情况,先求出5x-4y=1的特解：再乘以3得到原方程的一组特解:所以方程的通解为: t z情形3:若（a,b）|c,设,则方程（1）有特殊解例7求的一组特解解：因为，所以方程的特解为（-10，10）例8求的一组特解。解：因为，所以方程的特解为（2，-2）由情形2，情形3可以得到如下两种特殊情形；（1） 若，则方程有特殊解（2） 若，则方程有特殊解情形4:若，设，则方程（1）有特殊解例9求的一组特解解：因为，所以方程有特解（-3，3）受文献3的启发，本文进一步考虑了以下几种容易由观察法求出特解的情形：情形5:能观察出整数n使，设,则方程有特殊解例10求的一组特解解：因为：，所以方程有特解：（9，3）。例11求的一组特解解：因为，所以方程有特解：（4，2）情形6：能够观察出整数n，使，设，则方程有特殊解例12求方程的特解解：因为，所以方程的特解为：（6，-2）情形7:能够观察出整数j使设，则方程（1）有整数解例13解：因为，所以方程有特解为：（3，6）情形8:能够观察出整数j使得设，则方程（1）有整数解。例14求的一组特殊解解：因为：，所以方程有特解：例15求的一组特解解：因为，所以方程有特解情形9:能观察出整数使,则方程有特殊解。例16解：因为所以方程的一组特解为。例17解：因为，所以方程的一组特解为（6，4）。情形10:能够观察出整数使。则方程有特殊解。例18求的一组特解解：因为，所以方程的一组特解为：2. 2辗转相除法：辗转相除法又叫欧几里得算法，这种算法实际上是对整个不定方程用辗转相除法，依次化为等价的不定方程，直到有一个变元的系数为为止，这样的不定方程是可以解出来的，再依次反推上去就可以得到原方程的解，为了减少运算次数，在用带余除法时，我们总是用绝对值较小的作除数，如果这种方程无解，则实施这种运算时，到某一步就可以直接看出。例19，107 x+37y=25的一切整数解解：由给定的方程得：y=-2x+令y*=则y*应该是整数，故得一新的不定方程:y*+33x=25又: x=仿前又得到一个新的不定方程：x*+4y*=25又因为：y*=6-8x*+,可令：y*=即得： x*+4y*=1显然最后一个方程的解是：x*=1-4t,y*=t, t Z.再依次往回代入倒数第二个方程算出：x*=1-4t,y*=-2+33t依次类推得： x=3-37t最后求得不定方程的解为:(t Z.)2.3参数法：大家可以看到辗转相除法原理虽然容易掌握，但运算比较复杂，一直要除到系数为1为止，但是在某些情况下，我们只需要在“辗转相除”的基础上加以讨论设定参数即可，对于此法中学生可以掌握。例20求方程19x+1=17y+14=12z+1的正整数解：解：由方程化为方程可得：又因为x,y,z均为整数可令z=19t,由,得y+13=228t所以可得到：令：则可以算得：y*=5,t=14由此得可得方程的一组最小整数解：x=168,y=187,z=266例21九章算术中有这样一道题目：今有物，三三数之剩二，五五数之剩三，七七数之剩一，问其几何？解：设此数为x，又设y,z,u则由题意列方程组：或：3y+2=5z+3=7u+2由此得：3y=7u,y= u,因为y为整数，u z，设：y=7t,于是x=21t+2.其中t z,由此可算得当t=1时x取得最小值23。例225“五家共井”问题，五家合用一口井，各的绳子不一样长，而且都太短，井的深度等于甲家绳长的2倍加上乙家的绳长，或等于乙家绳长的3倍加上丙家的绳长，或等于丙家绳长的4倍加上丁家的绳长，或等于丁家的绳长的5倍加上戊家的绳长，或等于戊家的绳长的6倍加上甲家的绳长，问井有多深？解：设井深为w个单位长，各家绳长分别为a,b,c,d,e个单位长，则由题意得到方程组：由第一个式子得b=w-2a，再带入第二个式子c=6a-2w,依次带入得：d=9w-24a, e=120a-w, 265w-721a=0令： w=721t, a=265t, b=191t, c=148t, d=129t, e=76t, t z把t的值代入方程就可得到井的深度，当然井的深度不能为负，也不能无限的长，所以井的至少有721个单位长。在中学的教学中我们也常常遇到如下的一些题目，其实质仍为求二元一次不定方程的整数解：例23 7设A=，B=求这两个集合的中的公共元素组成的集合。解：将集合A，B中的元素分别记作an, bm则an,=3n+2, bm=4m-1,这是个等差数列的通项令an= bm化为m=( n+1),由 n和m都属于整数可得到m是3的倍数，n+1是4倍数即可令m=3k,带入得bm=4 3k-1=12k-1,记 Ck=12k-1(k z)则数列Ck就是的元素构成的集合。所以：=例24.解”百鸡问题”中的不定方程7x+4y=100解:原方程可以转化为 y=25-,考虑到y是正整数,可设x=4t,y=25-7t,z=75+3t，又因为x0,所以y0,我们可以得到t,故方程的解是:,。另外，我们除了直接引用参数的方法外，还可以利用直线的参数方程。中学里常见的不定方程是二元一次方程，形如（1）式，它的解对应的几何图形在坐标平面上是直线，此时，直线上的格点则是不定方程（1）的整数解，所以我们在做“线性规划”找整数解的题目时，通常在可行域划方格找整数解，但这种方法实在过于复杂，可行性也很差，因此我们可以利用直线的参数方程来求解。例25求 15x+25Y=100的整数解解：方程可以化为3x+5y=20,其图象是过（0，4）的一条直线，且斜率 k=由直线的点斜式参数方程得： t z例26在高中数学得二册（上）有这样一道例题：要将两种大小不同的钢板，截成A，B，C三种规格。每张钢板可以同时截得三种规格的小钢板的块数如同下表所示：钢板类型 规格A规格 B规格 C规格第一种钢板 2 1 1第二种钢板 1 2 3今需要A，B，C三种规格的成品为15，18，27块。问各截这两种钢板多少张可得所需三种规格的成品，且使用钢板张数最少？解：设需要第一种钢板x张，第二种钢板y张，则线形约束条件为：目标函数为：z=x+y作出在一组平行直线，x+y=k中（k为参数）经过可行域内的点且和原点距离最近的直线，此直线经过x+3y=27和直线2x+y=15的交点A的直线方程为因为等式右边为分数，所只能向后取整数所以 x+y=12，而不定方程x+y=12的通解的参数方程为：代入不等式求得：，所以满足条件的t=3,4。即方程有两组解（3，9），（4，8）。答：要截得所需三种规格的钢板，且使得所截钢板的张数最少的方法有两种：第一种方法是第一种钢板3张，第二种钢板9张；第二种方法是：第一种钢板4张，第二种钢板8张。2.4. 8矩阵法：我们知道（1）式可以用辗转相除法求出一组整数解，然后可得出其一切整数解，如果将辗转相除法用矩阵的的初等变换来表示，则可以得到矩阵的方法，一般来说，这种方法有清楚，简洁的优点。例27.求12x+41y=1的一组整数解解:由原方程得矩阵:注意到最后的矩阵的第2行1列的值为1，可得到原方程的一组整数解:由定理1可知方程的通解为:其中t Z这一方法理论依据如下对于方程（1），设（a,b）=1,所以pa+qb=1,则x=p,y=q显然是一组解，而有:因此，若将矩阵变换到某一行为（1,p,q）的形式，则 x0=p,y0=q就是方程ax+by=1的一组特解，当然，我们可以把它推广到n元一次方程，也可以把右边的系数推广到c,只要把 c乘以单位矩阵即可,所以方程 ax+by=c的一组特解为：例28.解不定方程8x+13y=1解：由题目我们可以得到矩阵:从而得到一组整数解:所以由定理1可得通解为: t Z例29求461x+463y=10的解解：作矩阵：所以方程的一组特解为：所以方程的通解为：另外还可以利用矩阵法的特点由定理3易知()()-()=()例30.求169x+121y=2的通解解:对169,121用辗转相除法求得q1=1, q2=2,q3=1,q4=1,q5=11则所以P5=81,Q5=58,故原方程的特解为：x0=116,y0=-162所以通解为：我们还可以利用矩阵的列初等变换来求不定方程的解例3182x1+3x2+4x3=1解：由题目得矩阵：所以方程的解是：，其中ti属于整数。25连分数法：如果我们把（1）式中的a,b相除化为连分数的形式，再利用定理4可得，这种方法较为直观。在系数比较大的情况下，不易求得特殊解时，也可以运用此法。例32求不定方程205x+93y=5的解解：因为化为连分数为：=2，4，1，8，2，则由定理4得， n=5,所以前一近数为：，其中，p=44,q=97.所以通解为；，求得的解为: t Z例33.有一个爱好数学的人，他发现自己到1981年时的年龄正好等于他出生的那年各位数字的和，你能算出他现在几岁吗？解：一个人的年龄一般在100岁以内，假如此人出生在二十世纪为,到1981年的年龄为1981-即是81-（10x+y）,这个数字正好等于各位数字之和，得：81-（10x+y）=1+9+x+y化为11x+2y=71,由连分数解法可知：=5+，前一近数中p=5,q=1.由定理4可知通解为: k z由于x,y都是0到9的正整数，即k需满足条件:，所以只要取k=33,得到唯一解（5，8）。答：此人是1958年出生，现年为2005-1958=47。26取特殊模法：例34.解“百鸡问题”中的二元一次不定方程7x+4y=100解：因为（7，4）=1，100又能被整除，故原方程有解，对原方程两边取模4得：7x 0(mod4),即，故可设x=4t,t Z,代入方程得：y=75-2z,因此原方程的通解为：，t Z根据题意可得，解的范围应该在0到100内，所以求得的几组解为：,易见解答过程简洁，明了，不失为求整数解的好方法，但是在系数较大情况下，要选取一个恰当的模比较困难，因此，我们需要对具体问题做具体分析，在系数较大时，我们可以先用辗转相除法把系数化小，再利用取特殊模法。例35求72x+23y=845的整数解的通式解：此方程系数较大，先用辗转相除法，将系数变小：令：,解得：23u+3x=17同时对两边取模3得于是， u=3t*+1,t* Z代如上面的等式得y