初等数论二演示文稿课件.ppt

1、不定方程是指未知数个数多于方程个数，且对解有不定方程是指未知数个数多于方程个数，且对解有第二章第二章 不定方程不定方程一定限制（比如要求解为正整数等）的方程。一定限制（比如要求解为正整数等）的方程。是数论中是数论中最古老的分支之一。最古老的分支之一。古希腊的丢番图早在公元古希腊的丢番图早在公元3 3世纪就世纪就 开始研究不定方程，开始研究不定方程，因此常称不定方程为丢番图方程。因此常称不定方程为丢番图方程。中国是研究不定方程最早的国家，中国是研究不定方程最早的国家，公元初的五家共公元初的五家共井问题就是一个不定方程组问题，井问题就是一个不定方程组问题，公元公元5 5世纪的世纪的 张丘张丘建算经

2、建算经中的百鸡问题标志中国对不定方程理论中的百鸡问题标志中国对不定方程理论有了系有了系统研究统研究。秦九韶的大衍求一术将不定方程与同余理论联秦九韶的大衍求一术将不定方程与同余理论联系起来。系起来。百鸡问题说：百鸡问题说：“鸡翁一，值钱五，鸡母一，鸡翁一，值钱五，鸡母一，值钱三，鸡雏三，直钱一。百钱买百鸡，问鸡翁、母、值钱三，鸡雏三，直钱一。百钱买百鸡，问鸡翁、母、雏各几何？雏各几何？”。这是一个三元不定方程组问题。这是一个三元不定方程组问题。19691969年，莫德尔较系统地总结了这方面的研究成果。年，莫德尔较系统地总结了这方面的研究成果。近年来，这个领域更有重要进展。近年来，这个领域更有重要

3、进展。但从整体上来说，但从整体上来说，对于高于二次的多元不定方程，人们知道得不多。对于高于二次的多元不定方程，人们知道得不多。另一方面，不定方程与数学的其他分支如代数数论、另一方面，不定方程与数学的其他分支如代数数论、代数几何、组合数学等有着紧密的联系，代数几何、组合数学等有着紧密的联系，在有限群论在有限群论在有限群论和最优设计中也常常提出不定方程的问题，在有限群论和最优设计中也常常提出不定方程的问题，这就使得不定方程这一古老的分支继续吸引着许多数这就使得不定方程这一古老的分支继续吸引着许多数学家的注意，成为数论中重要的研究课题之一。学家的注意，成为数论中重要的研究课题之一。第一节第一节 二元

4、一次不定方程二元一次不定方程研究不定方程一般需要要解决以下三个问题：研究不定方程一般需要要解决以下三个问题：有解时决定解的个数。有解时决定解的个数。判断何时有解。判断何时有解。求出所有的解。求出所有的解。本节讨论能直接利用整除理论来判定是否有解，以及本节讨论能直接利用整除理论来判定是否有解，以及有解时求出其全部解的最简单的不定方程有解时求出其全部解的最简单的不定方程二元一次不定方程。二元一次不定方程。11(1)(,)(,)axbyca bZ a ba b c、定理设二元一次不定方程不全为零 有整数解的充要条件是：000000,1(,),(,),(,),xyaxbyca b a a b b a

5、b axbyc证：（必要条件）设为（）的一组整数解，则00(,),(,),(,).a b aa b ba b axbyc11(,),(,),00,(,)(2)a b ccc a b cZa bZabs tZasbta b（充分条件）若设而对且，则存在使得1111010100002(,)=,=1cascbtca b ccxscytcaxbycxy在（）式 两 端 同 乘 以得令，即 得，故（）式 有 一 组 整 数 解，.注：定理的证明过程实际给出求解方程（注：定理的证明过程实际给出求解方程（1）的方法：）的方法：11()(1)(1)(,)(1),(1)nnnnnnnnniQ aPbra bsQ

6、tP 由辗转相除法等可求得，取；1010(),(,)(,)cciiscsxtctya ba b再取；00(),(,)(,)1cciiixsyta ba b则就 为 方 程 组（）的 一 组 整 数 解。0011010122(1),(,=,1,(3)xxyya bd aa d bb dxxb t yya ttZ、定理设二元一次不定方程有一整数解，）则（）的一切整数解可以表成：0101()()031a xbtb yat证：首先，即（）是（）的解；0010101110101()()04()=(),(,)1,xya xxb yya xxb yya ba yyb xxtZ其次，设，是（）的任一解，则，（

7、）或则，即存在使011001101 1014()0()0yya tya tya xxa bta d xxa bdtxxbtxy 或，代入（）式得，或即，因此，可表成（3）的形式。174100 xy例、求的一切整数解。7411,2);xy利用观察法求出的一组特解（再写出方程的一切整数解232111175xy例、求的一切整数解.(321,111)3 75,3725xy解：方程有解，且同解于方程10723371(1)99,(1)2626,9 25,26 25,xyxyxy 而方程107的一解是：故原方程的一组整数解为：9 2537,26 25 107(0,1,2,)xt yt t 则原方程的一切整数

8、解为：311132175xy例、求的一切整数解.,111255(321,111)3 75,53725xy yxxyxy 解：令原方程化为321（）方程（）有解，且同解于方程107注：利用辗转相除法求（a,b)时，前提为a,b为正整数，且a大于b，因此求解此方程时可以考虑用变量替换。37259 25,26 25,xyxy 由例2方程107的一解是：107259 25,26 25,xyyxxy 故方程37的一解是：3217526 25+107,9 2537(0,1,2,)xyxt yt t 则原方程111的一切整数解是：3、下面通过具体例子介绍一种判定方程是否有解，及其求出其解的直接算法整数分离法

9、31073725xy例、求的一切整数解3725 107yx解：25 107253323737xxyx 253333+3725(6)37xyxy令，则253725463333yyxy 同理（）254331=68(7)4yxxyx 令，则141(8)41 4,(0,1,2,)xyxyxt yt t 再令，最后得到则14,233(0,1,2,)xt yt t 则（7）的解为：233,337(0,1,2,)ytxyxt t （6）的解为：3 37,28 107(0,1,2,)xtyxyt t 从而原方程的解为：或先求出原方程的一个特解，再给出一切整数解。41(8)1,0;71,263,23,8xyxy

10、xyxyxy 的一个特解为从而（）的一个特解为；由此得到（）的一个特解为；最后得到原方程的一个特解为注：这种解不定方程的算法实际上是对整个不定方程用辗转相除法，依次化为等价的不定方程，直至得到一个变量的系数为正负1的方程为止。这样的不定方程可以直接解出。再依次反推上去，就得到原方程的通解。为了减少运算次数，在用带余除法时，总取绝对值最小余数。下面我们来讨论当二元一次不定方程（1）可解时，它的非负解和正解问题。由通解公式知这可归结为去确定参数t的值，使x,y均为非负或正。显见，当a,b异号时，不定方程（1）可解时总有无穷多组非负解或正解，理由是：000,0,000abtbxxtdayytd若有

11、无 穷 多 个 整 数，满 足所以下面只讨论a,b均为正整数的情形，先来讨论非负解：0,0,(,)11aba bcababcaxbycabccababab定理：设，当时，方程有非负整数解，解数等于或；当时，方程没有非负整数解。下面讨论正整数解：0,0,(,)1aba bcabcaxbycabccabab 定理：设，当时，方程有正整数解，解数等于-1或；当时，方程没有正整数解。例7、求方程5x+3y=52的全部正整数解解：x=8,y=4是一组特解，方程的全部解为：x=8+3t,y=4-5t正整数解满足8+3t0,4-5t084,2,1,035(8,4);(5,9);(2,14)tt 解得即对应有

12、：注：若只求方程正整数解的个数，可考虑以下不等式的整数解个数：0011xytba 784112,1,035tt 如 例，即 有 三 个 正 整 数 解。第二节 多元一次不定方程1 122(1)nna xa xa xN形如的方程称为多元一次不定方程。12(1)(,)nda aaN定理1方程有解的充分必要条件是121 122(1),nnnx xxa xa xa xN证：（必要条件）若方程有解则，121 12 2,nnnda aad axa xa xN因为（），所以21d Nnn充分条件：若,用数学归纳法证（1）有解。当时，已证成立；假定以上条件对元一次不定方程是充分的。1222 233(,)nnn

13、a add ta xa xN下面考察 元一次方程（1）。令，得到方程；12232 23323(,)(,),.nnnnnaaad Ndaad Nd ta xa xNtxx因 为，即，由 归 纳 假 设，方 程有 解1 1222 21222 212,a xa xd ta ad d txx考虑方程,由于()=则它有解，。1 1222 23312,1nnnnna xa xa xd ta xa xNx xx则故是（）的解。注：定理1的证明给出了n元一次不定方程的解法过程：即求解方程组（由n-1个方程组成）1 1222 22 2333 311nnnna xa xd td ta xd tdta xN2312

14、,nnt tt解前个二元一次方程时，应分别将看成常数；1321nnttt然后在此个方程的通解公式中分别消去，1n最终得到包含个独立的任意常数的通解。192451000 xyz例求的一切整数解。9 24 5110009243(1)351000(2)xyttz解：（，），方程有解，化为111(1)38383xytxttytttZ 等价于，通解为，222(2)351212000510003tztzttzttZ对，先求得的特解为：，故（2)的通解为，1112223832000510003xttytttZttzttZ ，22121220005,6000 158,200053,10003ttx ytxtt

15、ytttZzt 将代入消去 得就为所求的方程的解。21510661xyz例用整数分离法求解。1(61 1510)611022(1 32)6zxyxyxy解：原方程化为：1(1 32)611(631)3(1)22kxyZykxkxx令，得11(631)3(1)22ykxkxx1 33,6 105,ykm zmk mZ kZ 反推上去1(1)21 2,mxZxmmZ 再令，解得12133,6510 xmykmk mZzkm故 原 方 程 的 通 解 为进一步可求非负整数解：由通解公式给出非负整数解中m,k应满足1330,65100,120kmkmm1612,3521612,352mkmmmmm 由

16、此得即12321501mm解得故，160,0,135441,135mkkmkk 当时，则；当时，则；113141611xxxyyyzzz故原方程有三组非负整数解：第三节 勾股数222222,(),(),Rt ABCabca b ccxyzx y zx y z在中，我们有，其中表示两直角边长，表示斜边长，这就是著名的勾股定理，通常把二次不定方程称为商高方程或毕达哥拉斯方程，如果正整数满足不定方程，那么叫做一组勾股数。222222222+12=13+24=25+21=29在我国古代数学书周算经中，已经记载有“勾广三，股修四，经隅五三条边都是正整数的直角三角形，显然3,4,5满足方程（），刘峞的九章

17、算术注中载有：5，7，20由此看来，我国古代数学家已经找到了很多组满足方程（）的数，本节就对方程（）做系统的研究。首先我们来分析一下满足方程（）的解的特点。(1)0,;,0,;,0()0aaaaaxyz显然是方程满足的解。(2)0,(),(),()xyzx y zkZkxkykzd x d y d zxyzddd 若，是的解，（正负号任选）也是方程的解，（正负号任选）也是方程的解。2(3),0,(,)1(,)1,(,)1(,)1,(,)1,(,)1x y zx y zx ypp x p yp zp zx y zpx yy zz x当时，若则有素数满足从而于是即，矛盾，于是同理可得。222222

18、22(,)1,21,214()4()2,441,x yx yx yxmynxymnmnzkkxyzx yz由于，所以不同时为偶数，假设同时为奇数，则而或，矛盾。所以只能一奇一偶，从而 为奇数。0,0,0,(,)1,xyzx yx y因此为了求出（）的全部非零解，只要求出（）满足以下条件的解：一奇一偶。222211()0,0,0,(.)1,2(2)2,(3)0,(,)1,xyzx yxxab yabzababa ba b、定 理不 定 方 程的 满 足 条 件的 一 切 正 整 数 解 可 以 用 下 列 公 式 表 示 出 来：一 奇 一 偶。()0,0,0,2.xyzx证明：首先（3）是的解

19、，且22222222222222(,),2(,),12,21.dx ydxdydxyzd zd abd abda bdyd设，则，因此或 由于 不整除，故有再证满足条件（2）的解都可以表成（3）的形式。,()(2)(,)1(,)1,(,)1(,),2,2,(2,2)2(,)2,12,(,)2,(,)1x y zx yx zzx zxdzx zxdzx dzxz xdxzzx zxzx zx若是满足条件的解，因为，所以于是.（理由：设则或，但 是偶数 是奇数 所以因此）222()(),22yzx zxzxzxzxuzxvuvuvuvabuab vab于是由容易得到与都是奇数的平方，设，显然取，则

20、，22222222220,(),(),()()()()22()()()()2,22()()abzxabzxabzxzxababzabzxzxababxabyab abab显然于是因此，222222(,)1(,)222(2,2)2(,)1(,)1()(),z yzy zyzyazybaba ba byab ababa b因为，并且都是奇数，所以，又因为，所以，从而，再因为 是奇数，所以是奇数，是奇数 故一奇一偶。2222(,),(,),()2,()()x ydx y zdxabd yd abzd ab 注：一般地，假如那么因此的任意解可以表为：，2222xyz、不定方程的几何意义2221xyz求

21、不定方程的正整数解的几何意义就是要求边长为整数的直角三角形，这种三角形称为商高三角形，当商高三角形的三边长互素且为正整数时，称为本原商高三角形，定理 求出了所有的本原商高三角形。22(),0,()1(4)x y zzxyzz设方程的解为，当时，设，这样方程变为()0z不定方程的求解问题（）就等价于方程（4）的有理数解，的求解问题，在直角坐标平面上，方程（4）表示单位圆。因此，求方程（4）的有理数解就是求单位圆周上坐标为有理数的点，即有理点，于是立即得到2222222222223.22,0ababababababababa b、推论11单位圆周上的一切有理点可以表成及其中不全为，号可任取。例1、

22、求一个边长为整数的直角三角形，它的面积在数值上等于它的周长。222,()2()(5)2252x y zxyzxyzxyxyxyz解：设分别表示所述直角三角形的两直角边长和斜边长，则由（）式得()(448)004480488444xy xyxyxyxyxyxyxx代入式中并化简得由于，故222222,(4)841,2,4,85,6,8,1212,8,6,551213,6810512136810.x yxxxyy因为是正整数，由可知的值为，即，相应的 值为，但只有两组数符合条件，所以，所求的直角三角形只有两个，它们的边长分别为，或，例2、求不定方程（*）的满足条件0z26的全部互素的解。22126

23、5,abaa ba b解：由定理，得，又因为一奇一偶，求出的值即得到所求的解，结果列表如下：baxyz12345235121314158173472425例3、求z=65的满足方程（*）的全部正整数解。22()65()0(,)1,65,0651,5,13.k ababa ba bkkk解：由方程的解公式得，其中，一奇一偶，可取22221,6581748,1;7,416,63;63,16;56,33;33,56.kababxyxyxyxy当时即，相应的解为：2213,65135=13 212,1134=52,133=39;39,52.kabxyxy当时（）即，相应的解为：225,655 13=5

24、 323,25 12=60,5 5=25;25,60.kabxyxy 当时（）即，相应的解为：例5、假定(x,y,z)是(*)的解，并且(x,y)=1，那么在x,y中有一个是3的倍数，有一个是4的倍数，在x,y,z中有一个是5的倍数。2222,331,(31)31,31,3x ynnkxykzx y证明：假设都不是 的倍数，则它们的形状是其平方为因此的形状是它不是平方数，这与 是平方数矛盾 所以在中必有一个是 的倍数。2222,441,4+2(41)81,(4+2)=4,41414+24+2,18+28+5,4x ynnnknkx ynnnnx yxykkx y假设都不是 的倍数，则它们的形状

25、是，它们的平方是8，如果都是形如的数或一个是，一个是（不能同为，否则（），则的形状是或，它们都不是平方数，矛盾 所以在中必有一个是 的倍数。222222,551,52(51)51,(52)=1525,5x yznnnknkxykkxyzx yz假设，都不是 的倍数，则它们的形状是，但5，因此的形状是或，对前者不是平方数，对后者 是5的倍数 这都与假设矛盾，所以在，中必有一个是 的倍数。注意：定理中所说的在x,y中有一个是3的倍数，有一个是4的倍数，并不是说在x,y中一个是3的倍数，另一个是4的倍数，很可能3的倍数与4的倍数是同一个数。如（5,12,13），又如（11,60,61）2222222

26、42,(,)1(2),2,2xyzx zxabyab zab 例、证明：的整数解可以表示为222,)1,2x zx zxyz证明：因为（所以同为奇数 或一奇一偶，但若取一奇一偶，则与矛盾，故只能同为奇数。(,),2,2,(2,2)212,2.,4,42,12zx zxddzdxdzxddzx zxzxzxzxzx设则，或 由上分析有于是不能都是 的倍数也没有奇数公因子，如果不是 的倍数，那么为奇数 因此2222222(),22,(2)22,2,2zxzxyzxzxzxazxbxabyab zab由得知奇数及偶数都是平方数设，因此得22222224()2+=(2b),2(2),2,2.zxzxy

27、zxzxz xaxabyab zab 如果不是 的倍数，那么由令=即得命题得证22253,(,)10,0,0 xyzx yxyz例、求出不定方程,的一切正整数解公式3、无穷递降法1659年，法国数学家费马写信给他的一位朋友卡尔卡维，称自己创造了一种新的数学方法.由于费马的信并没有发表，人们一直无从了解他的这一方法.直到 1879年，人们在荷兰莱顿大学图书馆惠更斯的手稿中发现了一篇论文，才知道这种方法就是无穷递降法.无穷递降法是证明某些不定方程无解时常用的一种方法.其证明模式大致是:先假设方程存在一个最小正整数解，然后在这个最小正整数解的基础上找到一个更小的构造某种无穷递降的过程，再结合最小数原

28、理得到矛盾，从而证明命题.无穷递降法在解决问题过程中主要有两种表现形式:其一，由一组解出发通过构造得到另一组解，并且将这一过程递降下去，从而得出矛盾;其二，假定方程有正整数解，且存在最小的正 整数解，设法构造出方程的另一组解(比最小正整数解还要小)，从而得到矛盾.无穷递降法的理论依据是最小数原理.442(2)0 xyzxyz定理不定方程没有的整数解.00001111022,xyzzx y zzz证明：显然只要证（）无正整数解即可，用反证法，假若（）有正整数解，那么在全体正整数解中，必有一组解使得 取最小值 我们要由此找出一组正整数解满足，得出矛盾。42200000000002220000000

29、0()(,)1,2,(,)12.ixyp xyp zp zxyzzpppxyzxyzxx必有否则就有推出因此也是（）的正整数解，这与 的最小性矛盾，因此是（）的本原解，则必为一奇一偶 以及，不妨设NoImage4424220000000022210000100200124240000220000222220()()(),(,)(2,2)2,1,0,(,)1,()32iixyzyzxzxgzxzxgzxzxgzxvzxuuvu vzxzxu vuvxuv首先由得记，因为由此及2不整除即得由此可设，这里因同为奇数 所以也同为奇数，进而有（）222222222222222222222222(),();()2(2,2)2(,)2,22,12,(4)20,0,(,)12,2.uviiiguvguvuvguvuvuvuvguvuvababa bab记因为由 不整除，可推出不整除因此，由此可设这里，不整除02222(),(4)0,()2,()(0,(,)1,2,2,ivu vbuzv a uar srss rsrvrsarsurs由满足的条件及式推出及是方程的本原解且因此必有满足式解的条件不是的倍数）使得442004,(2),rsbr s bbzz由此及（）式的第二式即得这表明是方程的正整数解且有这与 的最小性矛盾，所以方程无正整数解。证毕