(4)-第二章-不定方程

初等数论-第二章不定方程.变数个数多于方程个数，且取整数值的方程(或方程组)称为不定方程(或不定方程组).本章讨论能直接利用整除理论来判断其是否有解，以及有解时求出其全部解的最简单的不定方程不定方程2,153100,100.3,74100.xyzxyzxyzzxy中国古代数学家张丘建曾经解答了下面的题目:鸡翁一,值钱五,鸡母一,值钱三,鸡雏三,值钱一.百钱买百鸡.问鸡翁母雏各几何?设,分别代表鸡翁、鸡母、鸡雏的数目,就得到下面的方程：消去再化简,即得我们要解决这个问题,就要求出上述方程的非负整数解301000111(,,,0),;(,),,,(1)0(1)-,(2)12,.abcabxxyyabdaadbbaxbycxxbtyyatdt定理1设二元一次不定方程其中是整数且都不是有一整数解又设则的一切解可以表成其中，，，400000101110000111,.()()().,',''',,(')(')0.,(xyaxbycaxbycaxbtbyatcbaabtctaxbycxyaxbycaxbycaxbycaxxbyyaadbbda证既然是的解,当然满足因此这表明对任何整数(2)式是的解.设是的任一解,则从此减去即得由上式及得到01011010101')-(').,,,1.,'-,'''-.','(2)(2)§32.1=+,..xxbyydababtyyatyyatyxxbtxyaxbyc又故由第一章推论可知有一整数使得亦即将代入上式即得因此可表成式的形状故式表示的一切整数解5000000110(,).,,,+=.(,),(,),(,),.,(,),(,),.31.1,,(,)axbycabcaxbycxyaxbycabaabbabaxbycabcccabcstasbtabxs定理2有整数解的充分与必要条件是证若有一整数解设为则但因而故必要性获证反之若则是整数由第一章推论存在两个整数满足下列等式令§1010000,,,(1),.cytcaxbycxy即得故式有整数解6121,02,01212717(10,7)1,1,117,110,0,1,2,249(18,24)69xxxxxtxttxx例1求10的解解所以方程有解,由视察法可得是一组特解.因此全部解是例2求18的解解由知无解|700(,);),,.axbycdabdcdcxy求解二元一次不定方程的方法：(i)求出最大公约数,并判断是否有(ii若即有解,则设法求出一组特解我们可以用辗转相除法来求特解,再根据定理1求出其所有解.82,,(,),1(,)(,),,,1,(,)=1(3),.,(3)1,.abaxbyabxyababxyaxbyaaxbyb由定理的证明在有解的情况下是先证明方程有解且与方程的解完全相同而在这个方程里未知数的系数是互质的所以只要讨论如何求出的方程的一个整数解容易看出由的一个特殊解得出方程的一个特殊解反之亦然911112221-2-1-1-1+1-1-1-10,0.,,0,,0,,0,.(,)1,1,31-(-1).[(-1)]-[(-1)]1.nnnnnnnnnnnnnnnnnnababqrrbbrqrrrrrqrrrrrqabrQaPbraQbP假定应用辗转相除法可以得到：因为故由第一章定理，于是§10-10111-1-201-1-22(-1),=(-1).(4)1,,,0,(3)31(5)(4),,1,,,2,,,5),(nnnnkkkknkkkkxQyPPPqPqPPQQQqqqQQknq因此式有一个特殊解：又由第一章定理由可以得出求的方法即先由辗转相除法求出把它们写在下表的第二横行里面：§114100.41,7,4,(,)1.xyxyabab例1求7的一切整数解解先解7此处2-1241(-1)1-1,(-1)22.-100,200.1-4-100,7200(0,1,2,)xyxyxyxtyyt因此7的一个解是故原方程的一个解是由定理其一切解可以表成1232175.(111,321)3,375,37-10725.107371.xyxyxy例2求111的一切整数解解而故有解,且原方程的解与的解完全相同今先解1322107371(-1)99,(1)262637-107126,9.37-107252625107,92537(0,1,2,)8107,337(0,1,2,)xyxyxyxyxyxtyttxtytt故的一解是的一解是故的一切解可以表成或14''1111'''1111111'11'00010,,,,0,,0.23,,,0,,1(6)''(71,),.qqrrabqrraxbycababbyrxbcbqrrbbrabxxyyrcaxyqb设给定一个适合下列条件的二元一次不定方程那么由带余数除法知道有整数满足条件又由第一章定理得到故方程有整数解设是(6)的任一整数解,则§'11010.(8)rrxqxb15'11'''1100110000'''111111,,','(7)'','',(,'(7)',','''9)xxyqqxyrrxyqqxyxxyybxyxyxyrryqqxyqqx但都是整数,因此则是的一个整数解,即(6)式的任一整数解能写成下列形状：其中是的某一整数解,反之,若是(7)的任一整数解,则由(9)式所得的是(6)的一解,这是因为由(7),(9)可以得出.xcaxbb16'11''11113,0,(,)1=',=-'+',=',=-'+'','''.31073725.axbycababxxyqqxyxxyqqxyxybyrxrxy定理的一切整数解可由得出只要中取式中的一切解例求的一切整数解17这种解不定方程的算法实际上是对整个不定方程用辗转相除法，依次化为等价的不定方程，直至得到一个变元的系数为1不定方程为止，这样的不定方程是可以直接解出的.再依次反推上去，就得到原方程的通解.为了减少运算次数，用带余数除法时，我们总取绝对最小余数.18122111311333433444544573121071(9072107)73113(17686)7311(17686)73111(73186)4(86)1761761(2786)17611(17686)73(135)27271(135)27(275xxxxxxxxZxxxxxxZxxxxxxZxx例4求907的解解556556)/132(5)/13(5)/13135xxxxZxx213661346663456664566663(258731)3(62176)44(62176)(1027)258731737(1027)3(513)6217622(513)1027xxxxxxxxxxxxxxxxxxxxxxx1912211131133343314344117213811(11738)62(94)21211(94)2111(214)2(34)991(34)911(94)31213xxxxxxxxZxxxxxxZxxxxx例求的解解最后一式表明:,不能同时为整数，所以不定方程无解20123331212124122414115115524154151066111(151061)2210(321)661(321)611(631)3(1)221(1)212,0,1,2,3133xxxxxxxxxxxxxxZxxxxxxxxZxxxxxxxxx例5求的全部解解的系数的绝对值最小，我们把原方程化为解得54531244545,0,1,2,22106510,,0,1,2,xxxxxxxxxx21§2多元一次不定方程111222,(1,),,,2,.+++=nnnaaaNnaxaxaxN定义多元一次不定方程其中是整数221212'''12'''1122'''1122(1)(,,,).(,,,)=.(i)(1),,,,++.3,++,.nnnnnnnaaaNaaadnxxxaxaxaxNdaxaxaxdN定理1式有整数解的充分必要条件是证设若式有解即有个整数满足等式则由第一章定理即这就证明了条件的必要性232122342233'''2311222(ii),(1).=2,12,(1).-1,.(,),(,,,,).,,,.nnnndNnnndaadaaadNdtaxaxNtxxaxaxdt若用数学归纳法证明式有解当时由定理式有解假定上述条件对元一次不定方程是充分的今证上述条件对元一次不定方程也是充分的令则由归纳法假定，方程有解,设其一解为再考虑§'2''12212'''''''1122332233'''12.12(,),,..,,,..nnnnnaadxxaxaxaxaxdtaxaxNxxx由定理及上式有解,设其一解为则故是(1)式的解这就证明了条件的充分性§24122233111222222333322111111(,),(,),,(,).261,|,(1);,(1)=,,,.nnnnnnnnnnnnnnnaaddaddaddNdNaxaxdtdtaxdtdtaxdtdtaxN求解多元一次不定方程的方法先顺次求出由第一章定理及上面定理若则无解若则有解.作方程首先求出最后一个方§1,nt程的一切解然后把的每一个值代入倒数第二个方程求出它的一切解,这样做下去即得出(1)的一切解.25924-510009243,383-51000.38,20005,13,10003,0,1,2,,0,1,2,.,6000158xyzxytxyttzxtutvytuzvuvtxvu例求的一切解.解(9,24)=3,(3,-5)=1,故方程有解.考虑方程即及由的方法得其中消去得§,200053,10003.yvuzv2612312312323122122121221123151066115,10,6.15,(15,10)5,(5,6)1.45661,15105151052,3,0,1,5661xxxaaagggyxxxyxxyxytxyttyxy例求的全部解解用定理3的方法来解.所以因此这不定方程等价于个变数、两个方程的不定方程组：的通解是的通解是223222112212321256,65,0,1,526,536,65,,0,1,txttyxttxttxttt消去就得到原不定方程的通解:27作业4P311,2求解以下方程(1)3x+5y=11(2)903x+731y=1106(3)1402x-1969y=2(4)x-2y-3z=7(5)5x+6y-4x=7(6)x+2y+3z=7,2x-5y+29z=1128