数论算法讲义3章同余方程.doc

第 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 f2） 同余方程的解若整数a使得 (a)≡0（mod m）成立，则a叫做该同余方程的解3） 同余方程的解数若a是同余方程（1）的解，则满足x≡a（mod m）的所有整数都是方程（1）的解即剩余类＝{x｜x∈Z，x≡a（mod m）}中的每个剩余都是解故把这些解都看做是相同的，并说剩余类是同余方程(1)的一个解，这个解通常记为x≡a（mod m）当均为同余方程(1)的解，且对模m不同余时，就称它们是同余方程(2)的不同的解，所有对模m的两两不同余的解的个数，称为是同余方程（1）的解数，记作显然≤m（4） 同余方程的解法一：穷举法任意选定模m的一组完全剩余系，并以其中的每个剩余代入方程（1），在这完全剩余系中解的个数就是解数。

例1】（例1）可以验证，x≡2，4（mod 7）是同余方程≡0（mod 7）的不同的解，故该方程的解数为2＋0＋1＝1≡3 mod 7＋1＋1＝3≡3 mod 7＋2＋1＝35≡0 mod 7＋3＋1＝247≡2 mod 7＋4＋1＝1029≡0 mod 7＋5＋1＝3131≡2 mod 7＋6＋1＝7783≡6 mod 7【例2】求同余方程≡0（mod 15）的解解）取模15的绝对最小完全剩余系：－7，－6，…，－1，0，1，2，…，7，直接计算知x＝－6，3是解所以，该同余方程的解是x≡－6，3（mod 15）且解数＝2例3】求同余方程≡0（mod 15）的解（解）同样直接计算知是解所以它的解是，解数为4例4】求解同余方程解）经直接计算知，本方程无解，即解数为0说明：当的系数都是模m的倍数时，显见，任意的整数值x都是同余方程（1）的解，这样的同余方程 （1）的解数为m但这并不是同余方程（1）的解数为m的必要条件例如 21＋35x＋14≡0（mod 7）显然，上方程等价于方程 0≡0（mod 7）【例5】由Fermat－Euler定理知，同余方程 的解数为5；同余方程 的解数为7。

一般地，对素数p，同余方程的解数为p例6】同余方程即的解数为35证）记，，，，由同余的性质，存在i，j使得成立（因5、7都是素数）直接计算：为奇函数，其余为偶函数x＝0时，≡0（mod 5），≡0（mod 7）x＝±1时，≡0（mod 5），≡0（mod 7）≡0（mod 35）即＝＝x＝±2时，≡5≡0（mod 5），≡21≡0（mod 7）即＝，＝x＝±3时，≡10≡0（mod 5），≡91≡0（mod 7）x＝±4时，≡15≡0（mod 5），≡273＝39·7≡0（mod 7）x＝±5时，≡±5≡0（mod 5），≡651＝93·7≡0（mod 7）x＝±6时，≡35≡0（mod 35），x＝±7时，≡50≡0（mod 5），≡±7≡0（mod 7）x＝±8时，≡65≡0（mod 5），≡63≡0（mod 7）x＝±9时，≡80≡0（mod 5），≡949·7≡0（mod 7）x＝±10时，≡±10≡0（mod 5），≡1443·7≡0（mod 7）x＝±11时，≡24·5≡0（mod 5），≡2109·7≡0（mod 7）x＝±12时，≡29·5≡0（mod 5），≡2983·7≡0（mod 7）x＝±13时， ≡34·5≡0（mod 5），≡24·7≡0（mod 7）x＝±14时，≡39·5≡0（mod 5），≡±14≡0（mod 7）x＝±15时， ≡±15≡0（mod 5），≡32·7≡0（mod 7）x＝±16时， ≡51·5≡0（mod 5），≡9399·7≡0（mod 7）x＝±17时， ≡58·5≡0（mod 5），≡11973·7≡0（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时，b≡c（mod m）ab≡ac（mod 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）设正整数d│m，那么，模m的同余方程（1）有解的必要条件是模d的同余方程 （2）有解ii）设方程（2）有解，它的全部解为（mod d） （3）那么，对（1）的每个解（如果有的话）a，有且仅有一个满足≡（mod d）（证）（i）设a是同余方程（1）的解，即(a)≡0（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））有两个解：方法一：利用方程≡0（mod 3）的解试探或穷举已知方程≡0（mod 3）的解为x≡0,1（mod 3），故由定理3.1.2知原方程的不同的解一定在集合{0，3，6，1，4，7}中逐个试验：以x≡0，3，－3，1，4，－2分别代入原方程中，可知x≡－3，0，3，4满足原方程，而x≡－2，1不满足原方程故原方程的解为x≡－3，0，3，4方法二：利用定理3.1.2，先求原同余方程相应于 (5)的解。

这时x＝3y＋0，代入原同余方程得显见，上式对所有y都成立因此，相应的全部解即为满足式（5）的全部x的值所以，原模9的同余方程有三个相应的解：x≡0,3,6（mod 9） 或x≡－3,0,3（mod 9）再求相应于 (6)的解这时，代入原同余方程得利用定理3.1.1，它可化为由定理3.1.2知，满足上式的y的值即为，即所以，y＝3k＋1，x＝3y＋1＝9k＋4，k∈Z因此，原同余方程恰有一个相应的解这样，由定理3.1.2推出，原同余方程的解数为4，即x≡－3,0,3,4（mod 9）【定理3.1.3】（i）若正整数，则满足模m的同余方程（1）的所有x的值（不是解数），与满足模的同余方程 （8）的所有x的值相同ii)且有 （9）（证）（i）显然（当d│(a,b,m)时，a≡b（mod m）a／d≡b／d（mod m）／d）ii) 设同余方程（8）的全部解为 （10）由前一部分结论知，满足模m的同余方程（1）的所有x的值（不是解数）即是由式（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】解同余方程解）选d=(6,9,6,15)=3，由定理3.1.3知，原方程与方程的解的值相同直接计算，同余方程有一个解：x≡2（mod 5）其解的所有值的集合为S＝{……－23，－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，…}即对原方程，其解为x≡2，7，12（mod 15）若用定理3.1.2的思路解方程，则是利用方程6x3＋9x2＋6≡0（mod 3）或6x3＋9x2＋6≡0（mod 5）的解再求原方程的解。

由定理3.1.1知方程6x3＋9x2＋6≡0（mod 3）的等价方程为0≡0（mod 3），故其解为x≡0，1，2由定理3.1.2知原方程的不同的解一定在集合{0,3,6,9,12；1,4,7,10,13；2,5,8,11,14}中若采用方法一，即逐个试验：以x≡0，1，…，14分别代入原方程中，可知x≡2，7，12（mod 15）满足原方程但定理3.1.2没有发挥作用若用方法二，还得再解3个方程6(3y)3＋9(3y)2＋6≡0（mod 15）、6(3y＋1)3＋9(3y＋1)2＋6≡0（mod 15）、6(3y＋2)3＋9(3y＋2)2＋6≡0（mod 15）才能获得原方程的解三) 一次同余方程的解设m┣a，那么，模m的一次同余方程为ax≡b（mod m） （11）【定理3.1.4】当（a，m）＝1时，同余方程（11）必有解，且其解数为1证法一 已知当时，x遍历模m的一组完全剩余系时，ax也遍历模m的完全剩余系，即若是模m的一组完全剩余系，则也是模m的一组完全剩余系因此，有且仅有一个使得即同余方程（11）有且仅有一个解证法2 当时，可知a。