初等数论第四章课件

一、基本概念及其一次同余式二、孙子定理第四章同余式四、高次同余式三、质数模的同余式同余式（方程）是同余理论的核心内容，本章仅介绍一些基本知识。第一节介绍有关同余方程的基本概念，讨论一次同余方程；第二节讨论一次同余方程组，证明了著名的孙子定理——实际上它也刻画了剩余系的整体性质；高于一次的同余方程在理论上至今也没有多少结果；第三节介绍求解高次同余方程的具体算法；第四节讨论素数模的同余方程。第一节基本概念及一次同余式1101()=1()0(mod)2nnnnfxaxaxafxmm、定义设整系数多项式（）将同余式（）叫做模的同余式（方程）。()0(mod)2aZfama若满足则称是同余式（）的解。(mod)2(mod)2xamxam显见，这时同余类中的任一整数也是同余式（）的解，我们把这些解都看作是相同的，也常说同余类是同余式（）的一个解。12,222.aammmmm当均为同余式（）的解，且对模不同余时才把它们看作是不同解，把所有对模两两不同余的（）解的个数称为是同余式（2）的解数。因此，只要取模的一组完全剩余系代入（）进行检验就可得到（2）的全部不同解，显然，模的同余式的解数至多为21427120(mod15)xx例、求同余式的解15,6,3x解：取模的绝对最小完全剩余系：-7,-1,0,1,7,直接代入检验知是解，6(mod15),3(mod15)xx所以同余式有两个解：0(mod)pxxppFermat注：①同余式有个解（由小定理可得）()()0(mod)2fxmsxm②同余式与（）等价特别地，一个同余式中系数为模的倍数的项去掉后，同余式的解不变。8636157453060(mod15)760(mod15)xxxxx例：同余式可化简为：20(mod)nammn、同余式的次数：若，则称模的同余式的次数是2()fx注③同余式（）的次数与多项式的次数不同。()2()()()(mod).0(mod)(mod)sxfxsxsxmaxbmaxbm④设是整系数多项式，同余式（）与的解和解数相同例与同解(,)12()0(mod)amafxm⑤设，同余式（）与同余式的解和解数相同()0(mod)()()()()()()()()(mod)2()0(mod).hxmmfxqxhxrxfxqxhxrxmrxm⑥设同余式有个解（即恒等同余式），如果或者那么同余式（）与同余式的解与解数相同7532532533()23610(mod5)()(21)()51(21)()1(mod5)1(mod5)fxxxxxfxxxxxxxxxxx例：所以原同余式化为一次同余式0(mod)(mod)0(mod)(1)axbmaxbmam一元一次同余式的一般形式或，()11(,)1(mod)mamxabm、一元一次同余式（1）当时有唯一解()1()()1(mod)(mod)1mmmaxaababbmxabm证：因为所以是（）的解。0,1,1(,)10,,(1)(mod)mmamamambmakbakm另外因为通过模的一个完全剩余系，并且，故，也通过模的一个完全剩余系，对于整数，存在模的完全剩余系中唯一整数与之同余，即，故方程（1）只有唯一解。021(,)011(mod)0,1,2,,1amdmdbdmxxkmkdd、定理：设，，同余式（）有解的充要条件是，此时（）恰有个解：，,,1mod(2)amdbddabmxddd（充分条件）若则因，故方程000(mod),.axbmaxbmydadmdb证：（必要条件）如果（1）有解，则有即，由可得000modmod,(2)1abmxxdddaxbm有唯一解，即则即满足的整数也满足（）.0001(mod)(mod)12.xaxbmabmxddd同时若有满足方程（），即，也有，即满足（）的整数也满足（）000=(mod)0,1,2,,1qdkxxmdmxmqkdmxkmkdd，（3）002(mod),0,1,2,mxxdmxxttdm故满足（）的全体整数，即必满足（1），此式对模来说，可以写成21830(mod42)x例求解0,0,1,2,,13mxkkdmdd但是对模两两不同余的，故（1）有个解，即（）(18,42)630635(mod7)x解：，同余式有个解，且等价于，4(mod7)411,18,25,32,39(mod42)xx经观察可得因此所求的6个解为，11a注：在实际求解时，可以不用公式，利用同余性质把（）中的变为即可210357(mod211)x例、求解(103,211)1解：因为，所以同余式有唯一解2206114(mod211)x两边乘以，得2115114(mod211)597(mod211)xxx即22104297(mod211)x两边乘以4，得2114297(mod211)65(mod211)xxx是所求的解3921(mod30)x例、求解(9,30)321解：，同余式有3个解930213107xyxy将同余式化为或1,1xy上述不定方程有一组解为1,9,19(mod30)x则同余式的3个解为：000(mod)(mod)*1axbmaxmybmybmmybyxa注：由得或，（）假设是它的解，则就是（）的解*am当时，求解（）式比解（1）方便，因此有时作此变换，即将模减小，简化计算，称之为交换模法4863880(mod2151)x例、求解2151880(mod863)42517(mod863)yy解：由原式得即17251(mod863)y用除两边得8631(mod25)z而131(mod25)z因此0251(mod13)1或0001251186322,691325880215169173863zyx所以(863,2151)1173(mod863)x因为，所以有唯一解：多元一次同余方程(mod)4,(,,)4.axbycmdcdabmmd定理：同余方程（）有解的充要条件是这里；且有解时，（）有个解0000,,,,xyZaxbycmtdadbdmdc证：（必要条件）若有解，则存在，使得，1111((,)(,)(,)(mod)damddbdbcbycd充分条件）设，则，由，有解1111(4)0(mod)(5)byccdaxcdm设，于是变为111(,)(5)(4)amdcd又因为，所以也有解，因此有解101(mod),0,1,,1,dyytdtdd111(mod)((,))bycddddbd另外，因为对模有个解：101dyytdkd它的每一个解1011()dmytdqrdd11(modmbycddmdd即)的个解对模来说是个解101(mod)dytdrmd10,1,,1,mrd其中111110(mod)(,),4axcdmamdmdddmd但有个解因此（）有个解，证毕.111(mod)(mod)bycdmmddaxbycmddm注：解二元一次同余方程的步骤:①先解，得到解的等式形式，对模有个解；②将上述解代入原方程得到个解，③联立①②就可以得到它的全部个解.357(mod12)xy例求解13,5,12,7,(,)3,(,,)17,12abmcdamdambddm解：方程有解，且有个解57(mod3)2(mod3)=2+3,0,1,2,3yyytt先解，得到，对模12有4个解：333(mod12)1(mod4),14,0,1,2xtxtxtss代入原方程得（*）解得即（*）的3个解为：23,14,0,1,2,3,0,1,2ytxtsts于是所求全部解为：这里，即1(mod12)3(mod12)7(mod12),,,2(mod12)2(mod12)2(mod12)xxxyyy2(mod12)2(mod12)6(mod12),,,5(mod12)5(mod12)5(mod12)xxxyyy4(mod12)0(mod12)4(mod12),,,11(mod12)11(mod12)1(mod12)xxxyyy3(mod12)1(mod12)5(mod12),,,8(mod12)8(mod12)8(mod12)xxxyyy一般地用数学归纳法不难证明同余方程1111(mod),(,,,),kkkkaxaxbmdbdaammd有解的充要条件为此时有个解第二节孙子定理我国古代的《孙子算经》里有问题如下：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？”“答曰二十三”.这是一个求解同余式组的问题，《孙子算经》已给出了求解方法，即为下面的孙子定理:12121122111222,,,,,1,2,,(mod)(mod)1(mod)(mod)21(mod)1,2,,kkiikkkkkiiimmmkmmmmmmMikxbmxbmxbmxMMbMMbMMbmMMmik定理1（孙子定理）设是个两两互质的正整数，，则同余式组（）的解是（）其中，111222,,(mod)ijkkkiiiiimMijxMMbMMbMMbMMbbm又因为故21,)11(mod)1(mod)iiiiiiiiMmMxmMMMm证：首先证（）是（）的解，因为(故必有解，即121212(mod),1,2,,,,)1,(mod),iijxxxxmikmmxxm其次证(1)的解是唯一的.设，都是适合(1)的两个整数，则因为(故故(1)的解只有(2)31(mod5)164(mod7)xx例、求解同余方程31(mod5)2(mod5)64(mod7)3(mod7)2(mod5)*3(mod7)17(mod35)xxxxxxx解：解得，解得，于是原方程等价于（）利用孙子定理解得31(mod5)164(mod7)xx例、求解同余方程31(mod5)2(mod5)64(mod7)3(mod7)2(mod5)*3(mod7)xxxxxx解：解得，解得，于是原方程等价于（）25,253(mod7),51(mod7)3(mod7)2521517(mod35)xyyyyxy解法2（代入法）：令则即，显然，因此所求的解为：31(mod5)164(mod7)xx例、求解同余方程31(mod5)2(mod5)64(mod7)3(mod7)2(mod5)*3(mod7)xxxxxx解：解得，解得，于是原方程等价于（）*2537,571(mod7)3,221531417xyzyzyzx解法3（化为二元一次不定方程）：由（）得即，显然所以：注：对模不互质的同余式组也可以同样引用孙子定理来求解3(mod8)11(mod20)1(mod15)xxx例2、求解解：把原方程中模化为质数幂的乘积，得3(mod8)11(mod4)11(mod5)1(mod5)1(mod3)xxxxx3(mod8)1(mod5)1(mod3)xxx易得原同余式组与下同余式组同解29(mod120)x利用孙子定理求解，得所求解为模不互质的同余方程组1122121212(mod)3(mod)(mod(,))(3)[,]xbm