数学奥赛辅导第四讲 不定方程

1数学奥赛辅导第三讲同余知识、方法、技能同余是数论中的重要概念，同余理论是研究整数问题的重要工作之一。本讲介绍同余的基本概念，剩余类和完全剩余系，同余方程，整数模的阶和中国剩余定理。Ⅰ.基本概念定义一：设m是一个给定的正整数。如果两个整数a、b用m除所得的余数相同，则称a、b对模m同余，记为a≡b（modm）；否则，记为a≡b（modm）。例如，15≡7（mod4），－23≡12（mod7）。同余有如下两种等价定义法：定义一*若m|a－b，则称a、b对模m同余。定义一**若a=b+mt（t∈Z），则称a、b对模m同余。同余的基本性质：（1）.|)(mod0amma（2）))((mod反身性maa))((mod)(mod)(mod))((mod)(mod传递性对称性mcamcbmbamabmba（3）若则),(mod),(modmdcmba①);(modmdbca②).(modmbdac（4）若).(mod,.,,2,1,0),(mod0101mbxbxbaxaxanimbannnnii则2特别地，设)(mod),()(01mbaZaaxaxaxfinn若，则).)(mod()(mbfaf（5）若).),((mod),(modcmmbambcac则特别地，又若（c，m）=1，则).(modmba【证明】因),(|bacm这等价于).(),(|),(bacmccmm又因若（a，b）=),(dbdad=1（d≠0）及b|ac，且（b，c）=1,|ab从而有).(|),(bacmm这个性质说明同余式两边的同一非零因数，不能像等式那样“约去”，只有当这非零因数与模互质时，才可“约去”。（6）),(modmba而).(mod),0(|dbadmd则（7）设),(modmba①若c0，则);(modmcbcac②d为a、b、m的任一公约数，则).(moddmdbda（8）若).(mod,1),()(mod),(mod212121mmbammmbamba则且（9）若).,(),(),(modmbmamba则Ⅱ.剩余类和完全剩余系若按对某一模m的余数进行分类，就可以引入所谓的剩余类和完全剩余系的概念。定义二：设m∈N*，把全体整数按其对模m的余数r（0≤r≤m－1）归于一类，记为kr，每一类kr（r=0，1，…，m－1）均称模m的剩余类（又叫同余类）。同一类中任一数称为该类中另一数的剩余。剩余类kr是数集)(mod|,,,|mraZaakZqrmrqmkrr且也即是余数是模，它是一个公差为m的（双边无穷）等差数列。根据定义，剩余类具有如下性质：3（1）);(,1210jikkkkkkZjim而（2）对任一数n∈Z，有惟一的00rknr使；（3）对任意的a，b∈Z，a，b).(modmbakr定义三：设110,,,mkkk是模m的（全部）剩余类。从每个kr中任取一个数ar，这m个数110,,,maaa组成的一个组称为模m的一个完全剩余系，简称完系。例如，取m=4，则有,9,5,1,3,7,,8,4,0,4,8,10kk，k2={…，－6，－2，2，6，10，…}，k3={…，－5，－1，3，7，11，…}。数组0，1，2，3；－8，5，2，－1等等都是模的4的一个完全剩余系。显然，模m的完全剩余系有无穷多个。但最常用的是下面两种：（1）非负数最小完全剩余系：0，1，2，…，m－1；（2）绝对值最小完全剩余系：它随m的奇偶性不同而略有区别。当.),1(,,1,0,1,),1(,,12kkkkkm为时（对称式）当).1(,,1,0,1,),1(,.),1(,1,0,1,),2(),1(,2kkkkkkkkm或为时由定义不难得到如下判别完全剩余系的方法：定理一：m个整数maaa,,,21是模m的一个完系iaji,时当≡)(modmaj定理二：设（b，m）=1，c为任意整数。若naaa,,,21为一个完系，则cbacbacbam,,,21也是模m的一个完全剩余系。特别地，任意m个连续整数构成模m的一个完全剩余系。【证明】只需证明：当).(mod,mcbacbajiji时而这可用反证法得证。下略。设m为一正整数，由于在0，1，…，m－1中与m互质的数的个数是由m惟一确定的一个正整数，因此，可给出如下定义。定义四：m为一正整数，把0，1，…，m－1与m互质的数的个数叫做m的欧拉函数，记为).(m4显然，)(m的定义域是正整数N*，前n个值为：,,6)7(,2)6(,4)5(,2)4(,2)3(,1)2(,0)1(当m=p为质数时，.1)(pp设k是模的一个剩余类。若a、b∈k，则).(modmba于是由性质9知，（a，m）=（b，m）。因此，若（a，m）=1，则k中的任一数均与m互质。这样，又可给出如下定义。定义五：如果一个模m的剩余类kr中任一数与m互质，则称kr是与模m互质的剩余类；在与模m互质的每个剩余类中任取一个数（共)(m个）所组成的数组，称为模m的一个简化剩余系。例如，取m=6，在模6的六个剩余类中，,,13,7,1,5,11,1k,17,11,5,1,7,5k是与模6互质的剩余类。数组1，5；7，－7；1，－1；等等都是模6的简化剩余类。由此定义，不难得到：定理三:)(21,,,maaa是模m的简化剩余系)).(,2,1,,)((mod,1),(mjijimaamajii且定理四：在模m的一个完全剩余系中，取出所有与m互质的数组成的数组，就是一个模m的简化剩余系。这两个定理，前者是简化剩余系的判别方法，后者是它的构造方法。显然，模m的简化剩余系有无穷多个，但常用的是“最小简化剩余系”，即由1，2，…，m－1中与m互质的那些数组成的数组。由定理不难证得简化剩余系的如下性质定理。定理五：设)(21,,,maaa是模m的简化剩余系。若（k，m）=1，则)(21,,,mkakaka也是模m的简化剩余系。下面介绍两个有关欧拉函数的重要结论。其证明略。定理六：（欧拉定理）若（a，m）=1，则)(mod1)(mam特别地，（费马小定理）若m=p为质数，pa，则).(mod11pap5定理七：（威尔逊定理）设p素数，则（p－1）！).(mod1p定理八：（欧拉函数值计算公式）令m的标准分解式为kkpppm2121，则kiipmm1).11()(例如，30=2·3·5，则.8)511)(311)(211(30)30(读者应认识到：由于任何整数都属于模m的某一剩余类，所以，在研究某些整数性质时，选取适当的（模）m，然后在模m的每个剩余类中取一个“代表数”（即组成一个完全剩余系），当弄清了这些代表数的性质后，就可弄清对应的剩余类中所有数的性质，进而弄清全体整数的性质，这就是引入剩余类和完全剩余系的目的。Ⅲ.同余方程设xaxaxaxaxfnnnn为0111)(的整系数多项式。类似于多项式和代数方程式的有关定义，我们有定义六：同余式)(mod0),(mod0)(mamxfn叫做一元n次同余方程。例如，)3(mod03539257xxx是七次同余方程。定义七：若c使得)(mod,)(mod0)(mcxmcf则成立叫做同余方程)(mod0)(mxf的一个解。显然，同余方程的解是一些剩余类，而不仅是一个或n个类。例如，),5(mod1x)5(mod4x都是二次同余方程)5(mod12x的解。1．一次同余方程)(modmbax（其中ma）称为一次同余方程。关于它的解，有如下共知的结论：定理九：若（a，m）=1，则)(modmbax有一个解。定理十：若（a，m）=d1，db，则)(modmbax无解，其中)(mod0ma。6定理十一：若（a，m）=d1，d|b，则)(modmbax有d个解。并且，若)(mod1mx的一个解为),(mod1mrx则d个解为：1,,1,0),(mod1dkmkmrx，其中.,,1dmmdbda下面介绍一次同余方程1),(),(modmambax（*）的解法。【解法1】因（a，m）=1，则存在二数s，t，使得as+mt=1，即)(mod1mas，由此有)(mod),(modmbsxmbsasx于是为（*）的解。【解法2】先把（*）变形成abmabx)((mod仅只是形式上的记号），然后用与m互质的数陆续乘右端的分子分母，直至把分母绝对值变成1（通过分子分母各对模m取余数）而得到解。【解法3】得用欧拉定理。因),(mod)(mod),(mod11)()()(mabxambaxmammm可得由从而有解).(mod1)(mabxm2．一次同余方程组定义八：若数r同时满足n个同余方程：rnkmxfkk则.,,2,1),(mod0)(叫做这n个同余方程组成的同余方程组的解。定理十二：对同余方程组).(mod),(mod2211mcxmcx记.],[,),(2121Mmmdmm①若d21cc，则此同余方程组无解；7②若21|ccd，则此同余方程组有对模M的一类剩余解。Ⅳ.模m的阶和中国剩余定理（1）模m的阶定义九：设m1是一个固定的整数，a是与m互素的整数，则存在整数k，1≤k＜m，使得)(mod1mak。我们将具有这一性质的最小正整数（仍记为k）称为a模m的阶。a模m的阶具有如下性质：①设makma模是,1),(的阶，,u是任意整数，则)(modmaavu的充要条件是)(modku。特别地，)(mod1mau的充分必要条件是k|u。【简证】充分性显然。必要性。设).(mod11),()(mod,,mamamaaululu易知及则由记用带余除法，krmamaakrrkqlrrkq0).(mod1),(mod1,0,由即故这里及k的定义知，必须r=0，所以).(modkru②设ama,2),(模m的阶为k，则数列,,,,32aaa模m是周期的，且最小正周期是k，而k个数kaaa,,,2模m互不同余。③设ama则,1),(模m的阶整除欧拉函数).(m特别地，若m是素数p，则a模p的阶整除p－1。（2）中国剩余定理（即孙子定理）设nmmmn,,,,221是两两互质的正整数，记M=niiiinimMMm1),,2,1(,则同余方程组),,2,1)((modnimcxii有且只有解niiiiMcMx1).(mod（△）8其中.,,2,1),(mod1nimMiii（△△）【证明】由)(1),(jimmji知，1),(jimM，因此每一个同余方程)(mod1iiymM（i=1，2，…n）都有解，于是必存在),(|,).(mod1,jiMmMmMmMiiiiiii又因使得所以对模).(mod),,2,1(111iiiiinnniiiimccMcMcMcMnim有故（△△）是（△）的解。若21,xx是适合（△）的任意两个解，则).(1),(,,,2,1),(mod21jimmnimxxjii因故),(mod),(mod212121Mxxmmmxxn即因此，（△△）是（△）的惟一解。9赛题精讲例1：数1978n与1978m的最末三位数相等，试求正整数m和n，使得n+m取最小值，这里.1mn（第20届IMO试题）【解】由已知而),1000(mod10781978mn1000=8×125，所以)8(mod10781978mn①)125(mod107819