初等数论第四章同余式

第四章同余式§1基本概念及一次同余式作为一个解。中的一切数，即成立，故把都能使中的任意整数，则剩余类的合理性：若定义的一个解。叫做成立的一个整数，则是使若称为次数。，则的同余式。若称为模，则，其中，设余方程）的求解问题。课题是研究同余式（同初等数论中的一个基本)(mod)(mod0)()(mod0)(2)(mod0)()(mod)(mod0)()(mod0)(mod0)()(011maxKmafaKmafmxfmaxmafanmammxfaaxaxaxfmaaninnnn定义2定义1ZZ。，解数为，的解为同余式，所以，，的一切整数解为因为不定方程。有解不定方程有解同余式的任一个解。是同余式其中，，个解，它们是余式共有。当此条件成立时，同有解的充分必要条件是，则一次同余式设ddkmdmkxxmbaxttdmxxbmyaxbdbmyaxmbaxmbaxxdkmdmkxxdbdmbaxdma1,,1,0)(mod)(mod)2(|)(mod)1()(mod1,,1,0)(mod|)(mod),(0000Z证明定理。解时，一次同余式有唯一当)(mod1),(1)(mbaxmam注同余式的解法1、代入法（适用于模较小时）。，得的完全剩余系逐一代入以，，所以同余式有唯一解因为解同余式)17(mod6171)17,3()17(mod13xx解例12、公式法（适用于模较小时）。从而，，，所以同余式有唯一解因为解同余式)11(mod8656)2()2()3(98981)11,8()11(mod98491101)11(xx解例23、变换系数法。故于是，可得再由，即于是，可得由，，所以同余式有唯一解因为。故，，而，，所以同余式有唯一解因为。，故而，，所以同余式有唯一解因为。；；解下列同余式)211(mod14665)211(mod654297)211(mod4297210)211(mod975)211(mod975)211(mod1145)211(mod114206)211(mod571031)211,103()3()31(mod13)31(mod9160297)31(mod5827141)31,14()2()15(mod4)15(mod16141)15,4()1()211(mod57103)3()31(mod2714)2()15(mod14)1(xxxxxxxxxxxxxxxx解例34、换模法的解。是的解，则是方便，而且若比解时，解当，后可得，模可得由)1()2()1()2(0)2()(mod)1()(mod000amybxymaabmyamybaxmbax是原同余式的解。即，，，，所以，，也即即，后得，模再化为，即，后得，模再化为，，也即即，后得，模原同余式可化为，，从而同余式有唯一解，故是质数，且因解同余式)2151(mod1731738636921518806985786317671318561)13(mod1)13(mod77)13(mod6851385613)85(mod613)85(mod1768638586317685)863(mod17685)863(mod880425)863(mod880215186321518808631)2151,863(2151|863863)2151(mod8808630000xxyzuuuuuzzzzyyyyyxx解例45、辗转相除法。所以，后得模，利用辗转相除法可得，，所以同余式有唯一解因为解同余式)2151(mod173880496)2151(mod18634962151121511998634961)2151,863()2151(mod880863xx解例5，。，，因此原同余式的解为，，解得由原同余式可得个解，，所以同余式有因为解同余式)33(mod30198)11(mod8)11(mod52315|3)33,6()33(mod156xxxx解例6§2孙子定理本节讨论同余式组)(mod)(mod)(mod2211kkmbxmbxmbx，，，的求解问题。。一个解因此，原同余式组只有，，于是，则两个整数，是适合同余式组的任意若是原同余式组的解。故，于是，，，所以又因为，，，则有一解，设为，于是，所以，因为。，其中，的解是，，，，则同余式组，，是两两互质的正整数，设)(mod)(mod,,2,1)(mod,)(mod)(mod|,,2,1)(mod1)(mod11),(1),(,,2,1)(mod1)(mod)(mod)(mod)(mod,,2,1,,,22211121212122211122211122211122112121mbMMbMMbMMxmxxkimxxxxmbMMbMMbMMxmbbMMbMMbMMbMMjiMmMmmkimMMMmxMMmjimmkimMMmbMMbMMbMMxmbxmbxmbxkiMmmmmmmmmmkkkikkkiiiiikkkijiiiiiiiiiijiiiikkkkkiikk证明定理1（孙子定理），当然有解。于，从而原同余式组等价使于是有，，这里，所以，同余式因为对充分性。必要性是显然的，下证有解。，同余式有解的充分必要条件是两两互质，则同余式组设正整数)(mod,),(mod),(mod)(mod1),(|)(mod,,2,1,,2,1)(mod)(mod,),(mod),(mod,,,222221111122211121kkkkkiiiiiiiiiiiiiiiiikkkkdmdbcxdmdbcxdmdbcxdmcdacmadbdmbxakikimbxambxambxambxammm证明推论1，矛盾。，，即则，这是因为若个数两两不同余。个数，这过，则令的完全剩余系。通过模的完全剩余系，则分别通过模若kimbbmbMMbMMmbMMbMMmmmmxbMMxmmmmmbMMbMMbMMxmmmbbbiiiiiiiiiikiiiikiiiikkiiiikkkkkk,,2,1)(mod)(mod)(mod)(mod,,,,,,1121010212221112121证明推论2定理1之所以称为“孙子定理”，因为在我国古代的数学著作《孙子算经》（纪元前后）中已经提出了这种形式的问题，并且很好地解决了它。孙子定理在国外文献和教科书中均称为“中国剩余定理”，并且在代数学中被推广成非常一般的形式。《孙子算经》中所提出的问题之一如下：今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何答曰：二十三。用现在的记号，上述问题相当于求解同余式组)7(mod2)5(mod3)3(mod2xxx，，。《孙子算经》中所用的方法可以列表如下：除数余数最小公倍数衍数乘率各总答数最小答数323×5×7=1055×7235×2×2140+63+30=233233-105×2=23537×3121×1×3723×5115×1×2程大位在《算法统宗》（1593）中将这一问题的算法总结成如下歌诀：三人同行七十稀，五树梅花廿一枝，七子团圆半个月，除百零五便得知。推广为一般的列表算法：除数余数最小公倍数衍数乘率各总答数m1b1m=m1m2…mkM1M1’M1M1’b1kiiiimbMMx1)(mod'm2b2M2M2’M2M2’b2……………mkbkMkMk’MkMk’bk。因此同余式组的解为得得得得解同余式，，，，，。解同余式组)2310(mod21013301385146231)5(mod12101)5(mod13301)6(mod13853)5(mod1462210765330116538511754621176231011765)11(mod),7(mod),6(mod),5(mod43214433221143214321bbbbxMMMMMMMMMMMMmbxbxbxbx解例1。故解为，则设兵数为。求兵数。一行纵队，则末行十人队，则末行四人，成十则末行五人，成七行纵行一人，成六行纵队，若列成五行纵队，则末韩信点兵：有兵一队，)2310(mod21116731102101433015385114623)11(mod10),7(mod4),6(mod5),5(mod1xxxxxx解例2有唯一解。余式组对模若上述条件成立，则同。，有解的充分必要条件是，同余式组],,,[,,2,1)),((mod,,2,1)(mod21kjijiiimmmkjimmbbkimbx定理2。可得原同余式组的解是，再解同余式组。代入得，得，代入可知由。先解同余式组。所以同余式组有唯一解，因为。解同余式组)120(mod113)8(mod1),30(mod23)30(mod23)2(mod1)10(mod3158)15(mod8)10(mod3),15(mod8))8,10((mod13)),8,15((mod18)),10,15((mod38)8(mod1),10(mod3),15(mod8xxxxyxyxxxxxxx解例3。由孙子定理可解得，即原同余式组可化为)120(mod113)2(mod1)3(mod2)5(mod3)2(mod1)2(mod3)5(mod3)3(mod8)5(mod833xxxxxxxxx另解§3质数模的同余式。为质数，，，其中式本节讨论质数模的同余)(mod0)()(mod0)()1(011papaxaxaxfpxfnnnnn等价。与因此，同余式，，于是，有由费马定理可知，，，知由多项式的带余除法可的质数模同余式等价。与一个次数不超过同余式)(mod0)()1()(mod)()()(mod01))(()()()()(1)1(pxrpxrxfpxxxpxrxrxqxxxfpppZ证明定理1论。，从而由归纳法可得结为质数，故，又，，则，令，，于是，所以因为是一个常数，次多项式，的个首项系数为是一，其中知由多项式的带余除法可。次多项式，首项系数为是一个，其中，个不同的解，则的是，，而设)(mod0)()(mod)(mod)()(0,,3,2)(mod)()()()(mod0)(mod0)(1)()()()()()(mod)()())(()()1(,,2,1)(mod11111111121pfpppfkixpxfxxfprpfrnaxfrxfxxfaknxfpxfxxxxfZxkkipxnkiiiiiinnkkki证明定理2。为奇质数时，时，结论显然成立；当当，，则中令在。，即首项系数为为零次多项式，，可知的解，于是由定理都是，所以由欧拉定理可知，因为。定理；，)(mod01)!1(2)(mod1))1(()2)(1(0)1()2()(mod))1(()2)(1(11)()(mod)())1(()2)(1(12)(mod011,,2,11,,2,11),()1()(mod01)!1()Wilson()2()(mod))1(()2)(1(1)1(1111ppppppxppxxxxxfpxfpxxxxpxppipippppxxxxxpkkppp