数论算法讲义 3章（同余方程）

1、第 3 章 同余方程（一） 内容：l 同余方程概念l 解同余方程l 解同余方程组（二） 重点l 解同余方程（三） 应用l 密码学，公钥密码学3.1 基本概念及一次同余方程(一) 同余方程（1） 同余方程【定义3.1.1】（定义1）设m是一个正整数，f(x)为n次多项式其中是正整数（0（mod m），则(x)0（mod m） （1）叫做模m的（n次）同余式（或模m的（n次）同余方程），n叫做f(x)的次数，记为deg f。（2） 同余方程的解若整数a使得 (a)0（mod m）成立，则a叫做该同余方程的解。（3） 同余方程的解数若a是同余方程（1）的解，则满足xa（mod m）的所有整数都是方程

2、（1）的解。即剩余类xxz，xa（mod m）中的每个剩余都是解。故把这些解都看做是相同的，并说剩余类是同余方程(1)的一个解，这个解通常记为xa（mod m）当均为同余方程(1)的解，且对模m不同余时，就称它们是同余方程(2)的不同的解，所有对模m的两两不同余的解的个数，称为是同余方程（1）的解数，记作。显然m（4） 同余方程的解法一：穷举法任意选定模m的一组完全剩余系，并以其中的每个剩余代入方程（1），在这完全剩余系中解的个数就是解数。【例1】（例1）可以验证，x2，4（mod 7）是同余方程0（mod 7）的不同的解，故该方程的解数为2。0113 mod 71133 mod 721350

3、 mod 7312472 mod 74110290 mod 75131312 mod 76177836 mod 7【例2】求同余方程0（mod 15）的解。（解）取模15的绝对最小完全剩余系：7，6，1，0，1，2，7，直接计算知x6，3是解。所以，该同余方程的解是x6，3（mod 15）且解数2。【例3】求同余方程0（mod 15）的解（解）同样直接计算知是解。所以它的解是，解数为4。【例4】求解同余方程。（解）经直接计算知，本方程无解，即解数为0。说明：当的系数都是模m的倍数时，显见，任意的整数值x都是同余方程（1）的解，这样的同余方程 （1）的解数为m。但这并不是同余方程（1）的解数为m

4、的必要条件。例如 2135x140（mod 7）显然，上方程等价于方程 00（mod 7）【例5】由fermateuler定理知，同余方程 的解数为5；同余方程 的解数为7。一般地，对素数p，同余方程的解数为p。【例6】同余方程即的解数为35。（证）记，由同余的性质，存在i，j使得成立（因5、7都是素数）直接计算：为奇函数，其余为偶函数x0时，0（mod 5），0（mod 7）x1时，0（mod 5），0（mod 7）0（mod 35）即x2时，50（mod 5），210（mod 7）即，x3时，100（mod 5），910（mod 7）x4时，150（mod 5），2733970（mod 7

5、）x5时，50（mod 5），6519370（mod 7）x6时，350（mod 35），x7时，500（mod 5），70（mod 7）x8时，650（mod 5），630（mod 7）x9时，800（mod 5），94970（mod 7）x10时，100（mod 5），144370（mod 7）x11时，2450（mod 5），210970（mod 7）x12时，2950（mod 5），298370（mod 7）x13时， 3450（mod 5），2470（mod 7）x14时，3950（mod 5），140（mod 7）x15时， 150（mod 5），3270（mod 7）x16时，

6、5150（mod 5），939970（mod 7）x17时， 5850（mod 5），1197370（mod 7）注意：由于本方程中x的幂都是奇数，故当x为其解释时，x也是其解。(二) 同余方程的性质【定理3.1.1】（i）若两个多项式f(x)g(x)（mod m），则同余方程（1）的解和解数与同余方程g(x)0（mod m）相同，此时称两个方程同解。（ii）若，则同余方程（1）的解和解数与同余方程相同。特别地，当时，取a（mod m），则多项式的首项系数为（证）（i）显然。（ii）因为时，有(x)0（mod m） a(x)0（mod m）（当(a,m)1时，bc（mod m）abac（mod

7、 m）【例6】证明同余方程（mod 15）与方程（mod 15）同解。（证）首先（mod 15），故方程（mod 15）与（mod 15）同解。其次，由于4（mod 15），所以，原方程又可以化简为()0（mod 15）0（mod 15）0（mod 15）另外，同余方程（mod 12）与方程（mod 12）同解。【定理3.1.2】（i）设正整数dm，那么，模m的同余方程（1）有解的必要条件是模d的同余方程 （2）有解。（ii）设方程（2）有解，它的全部解为（mod d） （3）那么，对（1）的每个解（如果有的话）a，有且仅有一个满足（mod d）（证）（i）设a是同余方程（1）的解，即(a)0

8、（mod m）从而由同余性质知 m(a)。已知，所以d(a)所以 (a)0（mod d），即（2）成立。（ii）又若有两个解和同时满足（mod d）， （mod d）则由同余的等价性之传递性知，必有（mod d）即（ii）成立。意义：方程（1）的解一定要在与方程（2）的解同余的数中去找。如a是（1）的解，是（2）的解，则必有kd，其中k为某个整数【例7】解同余方程。（解）考虑模5的同余方程 （4）由于由定理3.1.1知，方程（4）与方程的解相同。上式即容易验证它无解。因而由定理3.1.2知原同余方程无解。【例8】解同余方程。（解）由直接计算知，同余方程（即方程0（mod 3）有两个解：方法一：

9、利用方程0（mod 3）的解试探或穷举。已知方程0（mod 3）的解为x0,1（mod 3），故由定理3.1.2知原方程的不同的解一定在集合0，3，6，1，4，7中。逐个试验：以x0，3，3，1，4，2分别代入原方程中，可知x3，0，3，4满足原方程，而x2，1不满足原方程。故原方程的解为x3，0，3，4。方法二：利用定理3.1.2，先求原同余方程相应于 (5)的解。这时x3y0，代入原同余方程得显见，上式对所有y都成立。因此，相应的全部解即为满足式（5）的全部x的值。所以，原模9的同余方程有三个相应的解：x0,3,6（mod 9） 或x3,0,3（mod 9）再求相应于 (6)的解。这时，代

10、入原同余方程得。利用定理3.1.1，它可化为由定理3.1.2知，满足上式的y的值即为，即。所以，y3k1，x3y19k4，kz。因此，原同余方程恰有一个相应的解这样，由定理3.1.2推出，原同余方程的解数为4，即x3,0,3,4（mod 9）【定理3.1.3】（i）若正整数，则满足模m的同余方程（1）的所有x的值（不是解数），与满足模的同余方程 （8）的所有x的值相同。(ii)且有 （9）（证）（i）显然（当d(a,b,m)时，ab（mod m）adbd（mod m）d）。(ii) 设同余方程（8）的全部解为 （10）由前一部分结论知，满足模m的同余方程（1）的所有x的值（不是解数）即是由式（

11、10）给出的全部x的值（不是同余类）。由定理3.1.2知，对应于每一个同余类，恰好是模m的d个不同的同余类之和，由此就推出式（9）。证毕。【注意】定理3.1.2结论与定理3.1.3结论的区别（1） 定理3.1.2：方程（1）：(x)0（mod m）的解必满足方程（2）：(x)0（mod d），而方程（2）的解未必满足方程（1）。所以方程（2）的解集合包含方程（1）的解集合，从而可以在方程（2）的解中找方程（1）的解。（2） 定理3.1.3：方程（1）与方程（6）的所有解x的值相同，但解数不同，前者解数是后者的d倍。故可以先解相对简单的方程（6），再利用其解求方程（1）的解和解数。【例9】解同余

12、方程。（解）选d=(6,9,6,15)=3，由定理3.1.3知，原方程与方程的解的值相同。直接计算，同余方程有一个解：x2（mod 5）。其解的所有值的集合为s23，18，13，8，3，2，7，12，17，22，27，那么，由定理3.1.3的（i）知，s中每个值也满足原方程。但相对于原方程而言，s中包含了3类不同的解，即s，13，2，17，8，7，22，3，12，27，即对原方程，其解为x2，7，12（mod 15）若用定理3.1.2的思路解方程，则是利用方程6x39x260（mod 3）或6x39x260（mod 5）的解再求原方程的解。由定理3.1.1知方程6x39x260（mod 3）的

13、等价方程为00（mod 3），故其解为x0，1，2。由定理3.1.2知原方程的不同的解一定在集合0,3,6,9,12；1,4,7,10,13；2,5,8,11,14中。若采用方法一，即逐个试验：以x0，1，14分别代入原方程中，可知x2，7，12（mod 15）满足原方程。但定理3.1.2没有发挥作用。若用方法二，还得再解3个方程6(3y)39(3y)260（mod 15）、6(3y1)39(3y1)260（mod 15）、6(3y2)39(3y2)260（mod 15）才能获得原方程的解。(三) 一次同余方程的解设ma，那么，模m的一次同余方程为axb（mod m） （11）【定理3.1.4

14、】当（a，m）1时，同余方程（11）必有解，且其解数为1。证法一 已知当时，x遍历模m的一组完全剩余系时，ax也遍历模m的完全剩余系，即若是模m的一组完全剩余系，则也是模m的一组完全剩余系。因此，有且仅有一个使得即同余方程（11）有且仅有一个解。证法2 当时，可知a对模m有逆满足容易看出满足同余方程（11）。其次，若还有解也满足方程（11），则有，从而。即方程（11）的解数为1。特别地，按照证法二，并利用euler定理，同余方程（11）的解是（mod m） （12）【例9】解一次同余方程3x8（mod 20）。（解）用方法一、即穷举。令x0,1,2,19，经计算，可知3168（mod 20）

15、x16（mod 20）用方法二、因7（mod 20） x8785616（mod 20）【定理3.1.5】（定理1+补）一次同余方程（11）有解 (a,m)b。当方程（11）有解时，其解数为d(a,m)。而且，若是（11）的某个解，则它的d个解是，。此时称为方程（11）的一个特解，称上式为方程（11）的通解。（证）必要性：设方程（11）有解x（mod m） ，即满足ab（mod m），从而必存在使得abm即 amb而da， dm，故 damb。充分性：当d(a,m)1时，就是定理3.1.4。故假定d1。若db，则由定理3.1.3知，满足同余方程（11）的x的值和满足同余方程 （13）的x的值是相

16、同的。由于，故由定理3.1.4知同余方程（13）有解，所以同余方程（11）也有解。这就证明了充分性。其次，求方程（11）的解数：若是同余方程（11）的解，则它也是同余方程（13）的解，进而由定理3.1.4知，满足同余方程（13）的所有的x的值是（mod ） （14）由上面讨论知，式（14）也给出了满足同余方程（11）的所有的x的值（不是解数）。即由式（14）给出的模的同余类就是以下d个模m的同余类：即定理的后一半结论成立。【推论】（定理2）当(a,m)1时，一次同余方程x1（mod m） （15）有唯一解x（mod m）。【定义3.1.2】模m可逆元：设m是一个正整数，a是一个整数，。若存在整

17、数，使得1（mod m）成立，则a叫做模m可逆元，叫做a的模m逆元，记作a（mod m）。【定理3.1.6】（定理3）记d(a,m)，则一次同余方程（11）的全部解为， 。(四) 简化剩余的充要条件【定理3.1.7】（定理4）整数a是模m的简化剩余a是模m可逆元。(五) 一次同余方程的解法（1）穷举【例10】解一次同余方程6x9（mod 15）（解）方式一：针对原方程和模15穷举，即令x0,1,2,14，计算：r6x（mod 15）（0r14）600， 616， 6212， 633， 649， 650， 666， 6712， 683， 699， 6100，6116，61212，6133，614

18、9 原方程的解为 x4,9,14（mod 15）方式二：化原方程为解的值相同的等价方程2x3（mod 5） (16)再对模5穷举，即令x0,1,2,3,4，计算：r2x（mod 5）（0r4）200， 212， 224， 231， 243 方程(16)的解为 x4（mod 5）即原方程的解为 x4，45，4104，9，14（mod 15）【例11】解一次同余方程6x9（mod 14）（解）方式一：针对原方程和模14穷举600， 616， 6212，634， 6410， 652， 668， 670， 686， 6912， 6104，61110，6122，6138 原方程无解（2）公式：先判断，后

19、求解【例12】解一次同余方程12x18（mod 30）。（解）(12,30)6，618，所以原方程有6个解。等价方程2x3（mod 5） （17）解得x4（mod 5），即对模数5而言，剩余类集合xxz，x4（mod 5）,6,1,4,9,14,中每个剩余都是方程（17）的解，从而每个都是原方程的解。但对模数m5而言，中的所有元素都属于同一个剩余类，故只是一个解。也就是说方程（17）只有一个解。若这个解取最小正剩余，则有x4，若取最大非正剩余，则x1。而对模数m30而言，集合中的所有元素并不属于同一个剩余类，而且可以看出，当m30时，集合xxz，x4（mod 5）,6,1,4,9,14,19,

20、24,29,34,56,26,4, 34,64,51,21,9, 39,69,46,16,14, 44,74,41,11,19, 49,79,36, 6,24, 54,84,31, 1,29, 59,89,xxz，x4（mod 30）xxz，x9（mod 30）xxz，x14（mod 30）xxz，x19（mod 30）xxz，x24（mod 30）xxz，x29（mod 30）原方程有6个不同的解。即4，9，14，19，24，29（mod 30）【例13】解一次同余方程99x18（mod 143）。（解）(99,143)11，而1118，所以原方程无解。（3）利用展转相除法：axb（mod

21、m） （11）（i）取，由定理3.1.1知，同余方程（11）等价于同余方程 （18）（ii）同余方程（18）与同余方程 （19）同时有解或无解。这是因为同余方程（18）与不定方程同时有解或无解。而这不定方程可写为同样理由，上述不定方程与同余方程（19）同时有解或无解。（iii）若是（19）的解，则是（18），即（11）的解，这里 （20）反过来，若是(11)即(18)的解，则是（19）的解，这里 （21）此外，若，是（19）的两个不同的解，则相应地确定的，也是（18）即（11）的两个不同的解。所以（19）和（18）即（11）的解数相同。总结：以上的步骤（i）（ii）（iii）表明：求解模m的同

22、余方程（11），通过同余方程（18）转化为求解较小的模的同余方程（19）。如果（19）能立即解出，则由（20）就得到（11）的全部解；如果（19）还不容易解出，则继续对它用步骤（i），（ii），化为一个模更小的同余方程。这样进行下去总能使问题归结为求解一个模很小且能直接看出其是否有解的同余方程。再依次利用式（20）（即步骤（iii）反向推导即可求得（11）的全部解。【例13】解同余方程589x1026（mod 817）。（解）。这表明最后一个关于u的同余方程对模19有19个解：按（iii），即式（20）逐次反向推导得：关于对模38的同余方程有19个解，u0,1,18关于z对模95的同余方程有1

23、9个解：，u0,1,18关于y对模228的同余方程有19个解：，u0,1,18最后得到x对模817的同余方程有19个解：x(817y209)(228)(817(12u5)209)(228) 43u17 (mod 228)u0,1,18。注 在运用这一方法时，千万不能把搞错（特别是b1的正负号）。此外，如果在运用这方法过程中，利用同余式的性质化简同余方程时，改变了同余方程的模。则要注意方程的解数。例如，在例1中，当得到了同余方程 （22）后，如果利用同余的性质，就得到容易看出，满足这同余方程的所有的z的值是。但原来对z的同余方程的模为95，为了得到原方程（22）的解，就要利用定理3.1.3，得到

24、（22）有19个解：z25u，u0,1,18。【例13】解同余方程21x38（mod 117）。（解），最后的同余方程无解，所以原方程无解。3.2 中国剩余定理(一) 问题同余方程组孙子算经的“物不知数”问题：今有物，不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？答：23问题的建模：设物的总数为x，则x满足称为一次同余方程组。(二) 解法【定理3.2.1】（孙子定理、孙子剩余定理、中国剩余定理）设是两两互素的正整数。那么，对任意整数，一次同余方程组。 （1）必有解，且解数为1。并且有（i）若令，（i1,2,k）则同余方程组（1）的解是（mod m） （2）其中是满足 （i1,2

25、,k） （3）的一个整数（即对模的逆）。（ii）若令，（i1,2,k1）则同余方程组（1）的解可表为（mod m） （4）其中是同余方程组的解（i1,2,k），并满足递归关系式（mod ） （5）（i2,3,k）（证）证法一 由于，两两互素，故m （6）先证唯一性，即若同余方程组（1）有解，则必有（mod m）这是因为当均是同余方程组（1）的解时，必有 mod , i1,2,k由于两两互素，由同余的性质，从上式及式（6）即知唯一性成立。下面证由式（2）给出的 （7）确是同余方程组（1）的解。显见，所以满足式（3）的必存在。由式（3）及（）立知 mod ， i1,2,k即c是解。证法一虽然简单，

26、但很难看出为什么有形式（2）那样的解。证法二（构造性证明方法）用归纳法。当k1时，同余方程 mod 的解为x mod 当k2时，原同余方程组等价于同余方程组 （7）将上式的第一个方程的解x mod 表为x （8）（其中z为待定参数）。再将x 代入方程组（7）的第二式，有 mod 或 mod 已知(,)(,)1，故有() mod 其中1 mod 。代入（8）式，得方程组（7）的解为（() mod ） mod 设i1（i2）时，命题成立。即方程组有解 mod 对于i，同余方程组 （9）等价于方程组 （10）类似于k2时的情形，可将（10）中第一个方程的解表为x （11）（其中z为待定参数）。再将x

27、 代入方程组（10）的第二式，有 mod 或 mod 已知(,)(，)1，故有() mod 其中1 mod 。代入（11）式，得方程组（9）的解为（() mod ） mod 即（() mod ） mod 由数学归纳法，命题成立。(三) 例【例1】解“物不知数”问题。（解）（用公式）已知3，5，7，故m357105，。解方程，求（i1,2,k）：351（mod 3），得2（mod 3）211（mod 5），得1（mod 5）151（mod 7），得1（mod 7）由公式（2）得解为（mod m）352221131512（mod 105）233（mod 105）23（mod 105）即物品数可能为

28、23105k， （k0）最少为23。【例2】（韩信点兵）有兵一队，不到百人，若排成三行纵队，则末行一人；成五行纵队，则末行二人；成七行纵队，则末行五人。求兵数。（解）问题等价于解方程组。由上例知3，5，7时，m105，35，21，15，2（mod 3），1（mod 5），1（mod 7），从而有 x70121215518782（mod 105）规律：对方程 若模数3、5、7不变，则m、不变，故方程的解为x702115（mod 105） （12）韩信点兵：三人同行七十稀，五树梅花廿一枝，七子团圆正月半，除百零五便得知。又如：有兵一队，不到百人，若排成三行纵队，则末行一人；成五行纵队，则末行二人；

29、成七行纵队，则末行五人。求兵数。（解）此即解方程组由式（12）得x70121215582（mod 105）【例3】（逐次求解，对应证法二）求解 （13）（解）由第一个方程知 x2u1， u0,1,2（即针对第一个方程，有 x1（mod 2）代入第二个方程得 2u12（mod 3）解之得 u2（mod 3）即 u3v2， v0,1,2所以 x2u12(3v2)16v5， v0,1,2（即针对前两个方程，有 x5（mod 6）代入第三个方程得 6v53（mod 5）解之得 v3（mod 5）即 v5w3， w0,1,2所以 x6v56(5w3)530w23， w0,1,2 x23（mod 30）【

30、例4】（代入化简法）继续求解同余方程组（13）。1（mod 2） 2（mod 3） 3（mod 5） （解）化简过程：由方程知 x12y， y0,1,2 将代入方程、得12y2（mod 3）12y3（mod 5）即2y1（mod 3）2y2（mod 5）解之得y2（mod 3） y1（mod 5） （化为两个方程），再由方程得y23z 将代入方程得23z1（mod 5）解之得（化为一个方程） z3（mod 5） 回代过程：由 z35t， t0,1,2将z代入 y23(35t)1115t将y代入 x12(1115t)2330t x23（mod 30）【例5】（利用集合求交）求解方程组（解）孤立地

31、看问题，方程组中每个方程的解都是已知的，即方程的解为x1（mod 3），方程的解为x5（mod 8）。那么，解方程组实质就是求同时满足方程和的x。为此，给出两个方程各自解的值的集合a=, -11, -8, -5, -2, 1, 4, 7, 10, 13, 16, , 31, 34, 37, 40, b=, -11, -3, 5, 13, 21, 29, 37, 45, 而其共同解则为集合a与b的交，即ab=, -11, 13, 37, 所以x13（mod 24）是方程组和的共同解，从而也就是原方程组的解。【例6】（利用集合求交）求解方程组（解）先独立地解每个方程，得方程的解为x5（mod 7）

32、，方程的解为x2，6（mod 8）。为了求同时满足方程和的x，给出两个方程各自解的值的集合a=, -30, -23, -16, -9, -2, 5, 12, 19, 26, 33, 40, 47, 54, =, -30, -22, -14, -6, 2, 10, 18, 26, 34, 42, =, -10, -2, 6, 14, 22, 30, 38, 46, 54, 而其共同解的值的集合为a()=, -30, -2, 26, 54, 82, 110, 所以，原方程组的解为x-2, 26（mod 56）。【例7】计算（mod 77）（解）方法一：利用euler定理和模重复平方快速算法。首先，

33、(2,77)1，故1（mod 77）所以（mod 77）其次，利用模重复平方快速算法得，23（mod 77）所以 23（mod 77）方法2：将计算x（mod 77）化为小模数的方程组，利用解方程组求r。即x（mod 77） （注意1（mod 7），1（mod 11）解之得 23（mod 77）【例8】求相邻的四个整数，它们依次可被及整除。（解）设这四个相邻整数是。由题意知x应该满足，即解同余方程组问题。此时有，由定理3.2.1知。 所以满足要求的四个相邻整数有无穷多组，它们是2934844100t，2934944100t，2935044100t，2935144100t 0，1，2，最小的这样

34、的四个相邻正整数是：29348，29349，29350，29351【例9】（模数m1，m2，, mk不是两两互素）解同余方程组：（解）这里不两两互素，所以不能直接用定理3.2.1求解。容易看出，本同余方程组的等价方程组为显见，满足第一个方程的x必满足第二个方程，而第三，四个方程是一样的。因此，原同余方程组和同余方程组 （14）的解相同。同余方程组（14）满足定理3.2.1的条件。容易解出其解为注意到，所以这也就是原同余方程组的解，且解数为1。上例给出了模数不是两两互素时，求解同余方程组（1）的具体例子。【例10】解同余方程组。（解） 这不是定理3.2.1中的同余方程组的形式。容易看出，第二个同

35、余方程有解且解数为2：。因此，原同余方程组的解就是以下两个同余方程组的解： （15）及 （16）容易求出，同余方程组（15）的解是x31（mod 56）；同余方程组（16）的解是x3（mod 56）。所以，原同余方程组的解数为2，其解为3，31（mod 5）6【例11】解同余方程。（解） 这是一个一次同余方程，模数较大，求解不方便，但可以将其化为模较小的一次同余方程组来解，而且容易求解。由于，所以由同余性质知，原同余方程与同余方程组的解相同。整理可得典型的方程组进而，分别解同余方程组中的第二，第三，第四个方程，上述同余方程组就变为等价方程组再由定理3.2.1求解此方程组得。这就是原同余方程的解

36、。(四) 其它孙子定理是数论中最重要的基本定理之一。它实质上刻画了剩余系的结构。【定理3.2.2】在定理3.2.1的条件下，若分别遍历模的完全剩余系，则（mod m）遍历模的完全剩余系。（证）令（mod m）则当分别遍历模的完全剩余系时，遍历个数。下面证明这m个数模m两两不同余，从而构成m的一个完全剩余系，即定理结论成立。用反证法：假如对相应于的，存在另一组数，也使得（mod m）则应有（mod m）由同余的性质，上式成立的充分必要条件是 mod 即（注意当ji时，0 mod ） （i1,2,k） （3）但，故有， （i1,2,k）而、是同一个完全剩余系中的两个数，故， （i1,2,k）3.3

37、 高次同余式的解数及解法(一) 解数【定理3.3.1】（定理1）设两两互素，m，是整系数多项式。则同余方程 （1）与同余方程组 （2）等价。且这里表示同余方程的解数。也就是说，解数是m的积性函数。（证）由同余的性质知，当两两互素时， 即等价性成立。设方程 （3）的解是 （i1,2,k），则由中国剩余定理可求得一次同余方程组 （4）的解x（mod m）因为， （i1,2,k）故x也是方程（1）的解。因此，当遍历f(x)0（mod ）的所有解（i1,2,k）时，x也遍历方程（1）的所有解，即方程组（2）的解数为【例1】（例1）解同余方程0（mod 35）。（解）（用定理3.3.1求解）由定理3.3

38、.1知方程等价于同余方程组即 分别解单个方程，得各自的解为 的解为 x1，4（mod 5） 的解为 x3，5，6（mod 7）联立二方程的解，得方程组 （22）其解为（mod m）7353（mod 35）（m35，7，3，5，3）对不同的（，），设方程组（22）的解为a（mod 35）111444356356a31266241934说明：解方程组（22）的本质原因是求同时满足方程和的x：例如方程的一个解为x1（mod 5），方程的一个解为x3（mod 7），则二者解的值的集合为a=, -9, -4, 1, 6, 11, 16, 21, 26, 31, 36, b=, -11, -4, 3, 1

39、0, 17, 24, 31, 38, 而其共同解则为集合a与b的交，即ab=, -4, 31, 66, 所以x31（mod 35）是方程组（22）两个方程的共同解，从而也就是原方程组的解。(二) 特殊情形定理3.3.1的意义还在于指出了一般同余方程（1）（即同余方程组（2）的求解途径：即先解出每一个同余方程（3）的个全部解；然后，求一次同余方程组（4）的解；由这样得到的t个解就是同余方程（1）的全部解。当对某个j，同余方程（3）无解，则同余方程（1）也无解。通常，当时，取。这样，一般同余方程的求解就归结为模为素数幂的同余方程的求解。即求解 0 mod (5)设f(x)为整系数多项式，记称为f(

40、x)的导式。准备知识：f(abx)(bx)（按x 的升幂整理）【定理3.3.2】设x（mod p）是同余方程 0（mod p） (6)的一个解，且1则同余式（5）有解x mod 其中由下面关系式递归得到 （7）(i2,3, )。（证）用归纳法。(i) 2，相应于（5）的方程是 0 mod （8）由假设条件，方程（6）的解x（mod p）可表为p， 0,1,2代入（8）得关于的同余方程（希望选择某些以使上式满足方程（8） 0 mod 即0 mod 整理得 即 0 mod （9）由于是方程（6）的解，即 0（mod p），故p （或pq）。所以（9）可化为 （mod p） （10）由已条件知，1，

41、故方程（10）有唯一解 （mod p）由此得（8）的解（注意方程(10)的解可能有3类情形，此处为其一）（ii）设3i，并假设定理对i1成立，即同余方程 0 mod （11）有解，0,1,2 （12）为了求方程 0 mod （13）的解，将（12）代入（13）得关于的同余方程 0 mod 从中解出，即得（13）的解。为此，展开上式得0 mod 其中诸为整数。由于i2时，k(i1)i，故（k2,3,n）所以上式化简为0 mod （14）由归纳假设，是方程（11）的解，即 0 mod 亦即，从而（14）可化为 （mod p） （15）由（12）知（mod p），故（mod p）进而1所以（15）有

42、唯一解 （mod p） （mod p）代入（12），得（13）的解 （16）由归纳法原理，定理3.3.2成立。【例2】解同余方程0 mod 。（解）（用定理3.3.2的证明思路求解）（1）1，解方程0（mod 3）即 x0（mod 3）得 x0（mod 3）即 xp03（0,1, 2,）（2）2，解方程0 mod （23）以 xp03 （24）代入（23），求满足条件的0 mod 整理得0 mod （25）两边同除以p3得22（mod 3） （26）解得1（mod 3）（即方程（26）的解为 13，0,1, 2,）（注：此时方程（25）的解为1，4，7（mod 9），但下边可以看出，对方程（2

43、3）而言，它们都对应一个解）代入（24）得满足（23）的解x0303(13)39，（0,1, 2,）即 x3（mod 9）（若以方程（25）的另一解 43（0,1, 2,）代入（24）式，则x0303(43)129，即方程（23）的解仍为x123（mod 9）（以方程（25）的另一解 73（0,1, 2,）代入（24）式，也得同样的结果）（3）3，解原方程0 mod （27）以 x39 （28）代入（27），求满足条件的0 mod 整理得90 mod （29）或 180 mod 两边同除以9得20（mod 3） （30）解得0（mod 3）即方程（30）的解为 03，0,1, 2,）代入（28

44、）得满足（27）的解x3939(03)327，（0,1, 2,）即 x3 mod 【例3】解同余方程0 mod 。（解）（用定理3.3.2的公式计算）（1）1，解方程0（mod 3）得 x0（mod 3）那么 5，且（，p）（5，3）1从而2（mod p）3（2）2，解方程0 mod （31）利用公式（7） （7）计算f(0)6，故1（mod 3）0313 mod （3）3，解原方程利用公式（7）计算f(3)00（mod 3）303 mod 还可以继续算下去f(3)00（mod 3）303 mod 【例4】（问题的本质）解同余方程0 mod 。（解）（1）1，解方程0（mod 3）得 x0（m

45、od 3）（即 xp03，（0,1, 2,）（2）2，解方程0 mod （32）由定理3.1.2知，上方程的解只能在xp03（0,1, 2,）中找，且对于模数而言，实际上最多只有3个不同的解0，3，6 mod （或0，3）以0，3代入方程（32）检验，知解为3 mod （3）3，解原方程0 mod （33）与上类似，上方程的解只能在x3，（0,1, 2,）中找，且对于模数而言，实际上也最多只有3个不同的解（0,1）6，3，12 mod 代入方程（33）检验，知解为3 mod 依次类推，当i1时，设方程的一个解为 mod 则当i时，相应于的解最多3个，其值为， mod 例如，4，相应于3 mod 的可能